[数学]图论及相关算法入门.ppt

图论及其算法 复旦大学 董佳明 图的概念 1.图是由顶点集合及顶点间的关系集合组成的一种数据结构 G(V,E)，图由边和点组成。 2.有向图和无向图：有向图的边是有方向的，x,y和y,x是两条边，在无向图中是一条边。 3.完全图：边数为n(n+1)/2的无向图，边数为n(n+1)的有向图 图的存储 1.邻接矩阵 a[i,j]表示i到j的边 2.邻接表pre，other，last pre[i]表示i这条边的前一条边 other[i]表示i这条边指向的点 last[i]表示i这个点连接的最后一条边 注意：都是有向边！！！ 邻接矩阵 这种数据结构比较简单，适合储存规模较小、边比较稠密的图。 readln(n) for i:=1 to n do for j:=1 to n do read(a[i,j]); 邻接表 事实上是一种链表，适合储存规模较大，边比较稀疏的图。 readln(n,m); //m是边数，n是点数 l:=0; for i:=1 to m do begin readln(p,q); inc(l);pre[l]:=last[p];last[p]:=l;other[l]:=q; inc(l);pre[l]:=last[q];last[q]:=l;other[l]:=p; end; //无向边就相当于两条有向边 图的遍历 图的遍历是对给定一个图，从其中的任一顶点出发顺序访问图中的所有顶点，每个顶点被访问一次。遍历的结果是将顶点排成一定的序列。图的遍历是求解图的连通、拓扑排序等算法的基础。通常有深度优先遍历和广度优先遍历两种方法。 深度优先遍历（邻接矩阵实现） var a:array[0..100,0..100] of longint; //邻接矩阵 v:array[0..100] of boolean; //访问标记 i,j,n:longint; procedure dfs(x:longint); var i:longint; begin v[x]:=true; //将这个点设为已访问 for i:=1 to n do if (a[x,i]=1) and (not v[i]) then dfs(i); //如果能到达这个点且未访问 end; begin readln(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); fillchar(v,sizeof(v),false); //初始设为false for i:=1 to n do if not v[i] then dfs(i); end. 广度优先遍历(邻接矩阵实现) var a:array[0..100,0..100] of longint; zt:array[0..10000] of longint; //广度优先有哪些信誉好的足球投注网站的队列 v:array[0..100] of boolean; i,j,n:longint; procedure bfs(x:longint); var l,r,p:longint; //l是队头,r是队尾 begin l:=0;r:=1; //初始化队头队尾 zt[1]:=x; //将起始点放在队头 while lr do begin //如果队中有元素,那么进行有哪些信誉好的足球投注网站 inc(l);p:=zt[l]; //取出队头元素 for i:=1 to n do if (a[p,i]=1) and (not v[i]) then begin inc(r); v[i]:=true; //访问标记 zt[r]:=i; //将刚刚做完标记的点放入队尾 end; end; end; begin readln(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); fillchar(v,sizeof(v),false); for i:=1 to n do if not v[i] then bfs(i); end. 图的最短路 给定带权有向图G=（V，E），其中每条边的权是非负实数，另外，再给定V中的一个顶点，我们称之为源点。要计算从源点到其他各顶点的最短路径长度。这个问题称为图论单源最短路问题。 Dijkstra、spfa、floyd Dijkstra 是一种贪心算法。 建立集合s，先将源点加入集合。把距源