《图的遍历与最小生成树.doc》由会员分享，可在线阅读，更多相关《图的遍历与最小生成树.doc（18页珍藏版）》请在金锄头文库上搜索。
1、二中信息学奥赛培训讲义图论1图的遍历与图的最小生成树一、图的遍历图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visitn作为对顶点的标记，当顶点vi未被访问，visiti值为0；当vi已被访问，则visiti值为1。有两种遍历方法（它们对无向图，有向图都适用） 深度优先遍历 广度优先遍历1、深度优先遍历从图中某顶点v出发： 1）访问顶点v；2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；对于给定的图G=（V，E），首先将V中
2、每一个顶点都标记为未被访问，然后，选取一个源点vV，将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，如果从v出发有路的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到V中所有顶点都已被访问过为止。例：在下图中，从V0开始进行一次深度遍历的过程如图所示：深度优先遍历得到的遍历序列为：序列1：V0,V1,V3,V7,V4,V2,V5,V6序列2：V0,V1,V4,V7,V3,V2,
3、V5,V6由于没有规定访问邻接点的顺序，深度优先序列不是唯一的。但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的。例如：对下图（a）的邻接表存储（图b）的遍历过程如图（c）。 图a 图b图cDFS序列：c0 c1 c3 c4 c5 c2采用邻接表存储结构的深度优先遍历算法实现：Pascal语言：procedure dfs(g:adjgraph;i:integer);var p:edgenode;begin writeln(visit vertex:,g.adjlisti.vertex); visitedi:=true; p:=g.adjlisti.firstedge;
4、 while pnil do begin if not visitedp.adjvex then dfs(g,p.adjvex); p:=p.next; end;end;procedure dfstraverse(g:adjgraph);var i:integer;begin for i:=1 to g.n do visitedi:=false; for i:=1 to g.n do if not visitedi then dfs(g,i);end;C语言：/*/* 图的深度优先遍历算法 */* 文件名：dfs.c 函数名：dfs()、dfstraverse() */*/int visite
5、dm;void dfs(adjgraph g,int i) /*以vi为出发点深度优先遍历顶点vi所在的连通分量*/ edgenode *p; printf(visit vertex: %c n,g.adjlisti.vertex); /*访问顶点i*/ visitedi=1;p=g.adjlisti.firstedge; while (p) /*从p的邻接点出发进行深度优先搜索*/ if (!visitedp-adjvex) dfs(g,p-adjvex); /*递归*/ p=p-next; void dfstraverse(adjgraph g) /* 深度优先遍历图g */ int i;
6、 for (i=0;ig.n;i+) visitedi=0; /*初始化标志数组*/ for (i=0;ihead) /*当队列非空时，执行下列循环体*/ j=queue+head; /*出队*/ p=g.adjlistj.firstedge; while (p) /*广度优先搜索邻接表*/ if (visitedp-adjvex=0) printf(%c ,g.adjlistp-adjvex.vertex); queue+tail=p-adjvex; visitedp-adjvex=1; p=p-next; int bfstraverse(adjgraph g,datatype v) int i,count=0; /*广度优先遍历图g*/ for (i=0;ig.n;i+) visitedi=0; /*初始化标志数组*/ i=loc(g,v); /*寻找顶点v在邻接表中的位序*/ if (i!=-1) count+; /*连通分量个数加1*/ bfs(g,i); for (i=0;ihead do begin inc(head); j:=queuehead; p:=g.adjlistj.firstedge; while pni
