二中信息学奥赛培训讲义 - 1 - 图论1——图的遍历与图的最小生成树 一、图的遍历 图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visit[n]作为对顶点的标记，当顶点vi 未被访问，visit[i]值为 0；当 vi 已被访问，则 visit[i]值为 1。 有两种遍历方法（它们对无向图，有向图都适用） 深度优先遍历 广度优先遍历 1、深度优先遍历 从图中某顶点v 出发： 1）访问顶点v； 2）依次从v 的未被访问的邻接点出发，继续对图进行深度优先遍历； 对于给定的图G=（V，E），首先将 V 中每一个顶点都标记为未被访问，然后，选取一个源点vV，将 v 标记为已被访问，再递归地用深度优先搜索方法，依次搜索 v 的所有邻接点w 。若 w 未曾访问过，则以 w 为新的出发点继续进行深度优先遍历，如果从v 出发有路的顶点都已被访问过，则从v 的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到 V 中所有顶点都已被访问过为止。 例：在下图中，从V0 开始进行一次深度遍历的过程如图所示： 深度优先遍历得到的遍历序列为： 二中信息学奥赛培训讲义 - 2 - 序列1：V0,V1,V3,V7,V4,V2,V5,V6 序列2：V0,V1,V4,V7,V3,V2,V5,V6 由于没有规定访问邻接点的顺序，深度优先序列不是唯一的。 但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的。 例如：对下图（a）的邻接表存储（图 b）的遍历过程如图（c）。 图 a 图 b 图 c DFS 序列：c0 c1 c3 c4 c5 c2 采用邻接表存储结构的深度优先遍历算法实现： Pas cal 语言： procedure dfs(g:adjgraph;i:integer); var p:edgenode; begin writeln('visit vertex:',g.adjlist[i]^.vertex); visited[i]:=true; p:=g.adjlist[i]^.firstedge; while p<>nil do begin if not visited[p^.adjvex] then dfs(g,p^.adjvex); p:=p^.next; end; 二中信息学奥赛培训讲义 - 3 - end; procedure dfstraverse(g:adjgraph); var i:integer; begin for i:=1 to g.n do visited[i]:=false; for i:=1...
VIP
