图的遍历与最小生成树

《图的遍历与最小生成树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二中信息学奥赛培训讲义图论1——图的遍历与图的最小生成树一、图的遍历图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组visit[n]作为对顶点的标记，当顶点vi未被访问，visit[i]值为0；当vi已被访问，则visit[i]值为1。有两种遍历方法（它们对无向图，有向图都适用）Ø深度优先遍历Ø广度优先遍历1、深度优先遍历从图中某顶点v出发：1）访问顶点v；2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；对于给定的图G=（V，E）

2、，首先将V中每一个顶点都标记为未被访问，然后，选取一个源点vÎV，将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，如果从v出发有路的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到V中所有顶点都已被访问过为止。例：在下图中，从V0开始进行一次深度遍历的过程如图所示：深度优先遍历得到的遍历序列为：-18-二中信息学奥赛培训讲义序列1：V0,V1,V3,V7,V4,V2,V5,V6

3、序列2：V0,V1,V4,V7,V3,V2,V5,V6由于没有规定访问邻接点的顺序，深度优先序列不是唯一的。但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的。例如：对下图（a）的邻接表存储（图b）的遍历过程如图（c）。图a图b图cDFS序列：c0®c1®c3®c4®c5®c2采用邻接表存储结构的深度优先遍历算法实现：Pascal语言：proceduredfs(g:adjgraph;i:integer);varp:edgenode;beginwriteln('visitvertex:',g.adjlist[i]^.vertex);visited[i]:=true;p:=

4、g.adjlist[i]^.firstedge;whilep<>nildobeginifnotvisited[p^.adjvex]thendfs(g,p^.adjvex);p:=p^.next;end;-18-二中信息学奥赛培训讲义end;proceduredfstraverse(g:adjgraph);vari:integer;beginfori:=1tog.ndovisited[i]:=false;fori:=1tog.ndoifnotvisited[i]thendfs(g,i);end;C语言：/**********************************************

5、***********//*图的深度优先遍历算法*//*文件名：dfs.c函数名：dfs()、dfstraverse()*//********************************************************/intvisited[m];voiddfs(adjgraphg,inti){/*以vi为出发点深度优先遍历顶点vi所在的连通分量*/edgenode*p;printf("visitvertex:%c",g.adjlist[i].vertex);/*访问顶点i*/visited[i]=1;p=g.adjlist[i].firstedge;while(p)/

6、*从p的邻接点出发进行深度优先搜索*/{if(!visited[p->adjvex])dfs(g,p->adjvex);/*递归*/p=p->next;}}voiddfstraverse(adjgraphg){/*深度优先遍历图g*/inti;for(i=0;i

7、调用一次dfs。从dfstraverse中调用dfs或dfs内部递归调用自己的最大次数为n。当访问某顶点vi时，dfs的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接表表示图时，需搜索第i个边表上的所有结点，因此，对所有n个顶点访问，在邻接表上需将边表中所有O（e）个结点检查一遍。所以，dfstraverse算法的时间复杂度为O（n+e）。2、广度优先遍历图中某未访问过的顶点vi出发：1）