图的遍历.

Presentation on theme: "图的遍历."— Presentation transcript:

1 图的遍历

2 图的遍历与连通性 从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 ( Graph Traversal )。 图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ]，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited [i] 为 1，防止它被多次访问。

3 深度优先搜索DFS ( Depth First Search )
深度优先搜索的示例

4 DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

5 图的深度优先搜索算法 template<class NameType, class DistType>
void Graph <NameType, DistType> :: DFS ( ) { int * visited = new int [NumVertices]; for ( int i = 0; i < NumVertices; i++ ) visited [i] = 0; //访问标记数组 visited 初始化 DFS (0, visited ); delete [ ] visited; //释放 visited } void Graph<NameType, DistType> :: DFS ( const int v, int visited [ ] ) {

6 cout << GetValue (v) << ‘ ’; //访问顶点 v
visited[v] = 1; //顶点 v 作访问标记 int w = GetFirstNeighbor (v); //取 v 的第一个邻接顶点 w while ( w != -1 ) { //若邻接顶点 w 存在 if ( !visited[w] ) DFS ( w, visited ); //若顶点 w 未访问过, 递归访问顶点 w w = GetNextNeighbor ( v, w ); //取顶点 v 的排在 w 后面的下一个邻接顶点 }

7 算法分析 图中有 n 个顶点，e 条边。 如果用邻接表表示图，沿 Firstout  link 链可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。 如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。

8 广度优先搜索BFS ( Breadth First Search )
广度优先搜索的示例 广度优先搜索过程 广度优先生成树

9 使用广度优先搜索在访问了起始顶点 v 之后，由 v 出发，依次访问 v 的各个未曾被访问过的邻接顶点 w1, w2, …, wt，然后再顺序访问 w1, w2, …, wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，… 如此做下去，直到图中所有顶点都被访问到为止。 广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。

10 为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。
为避免重复访问，需要一个辅助数组 visited [ ]，给被访问过的顶点加标记。 图的广度优先搜索算法 template<class NameType, class DistType> void Graph <NameType, DistType> :: BFS ( int v ) { int * visited = new int[NumVertices]; for ( int i = 0; i < NumVertices; i++ ) visited[i] = 0; //visited 初始化

11 cout << GetValue (v) << ' '; visited[v] = 1;
Queue<int> q; q.EnQueue (v); //访问 v, 进队列 while ( !q.IsEmpty ( ) ) { //队空搜索结束 v = q.DeQueue ( ); //不空, 出队列 int w = GetFirstNeighbor (v); //取顶点 v 的第一个邻接顶点 w while ( w != -1 ) { //若邻接顶点 w 存在 if ( !visited[w] ) { //若该邻接顶点未访问过 cout << GetValue (w) << ‘ ’; //访问 visited[w] = 1; q.EnQueue (w); //进队 } w = GetNextNeighbor (v, w); //取顶点 v 的排在 w 后面的下一邻接顶点

12 算法分析 } //重复检测 v 的所有邻接顶点 } //外层循环，判队列空否 delete [ ] visited; }
} //外层循环，判队列空否 delete [ ] visited; } 算法分析 如果使用邻接表表示图，则循环的总时间代价为 d0 + d1 + … + dn-1 = O(e)，其中的 di 是顶点 i 的度。 如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。

13 连通分量 (Connected component)
当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点。 若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。 在算法中，需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。

14 对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。

15 确定连通分量的算法 template<class NameType, class DistType> void Graph<NameType, DistType> :: Components ( ) { int *visited = new int[NumVertices]; for ( int i = 0; i < NumVertices; i++ ) visited[i] = 0; //visited 初始化 for ( i = 0; i < NumVertices; i++ ) if ( !visited[i] ) { //检测所有顶点是否访问过 DFS ( i, visited ); //从未访问的顶点出发访问 OutputNewComponent ( ); //输出一个连通分量 }

16 重连通分量 (Biconnected Component)
delete [ ] visited; //释放visited } 重连通分量 (Biconnected Component)  在无向连通图G中，当且仅当删去G中的顶点 v及所有依附于v的所有边后，可将图分割成 两个或两个以上的连通分量，则称顶点v为关 节点。 没有关节点的连通图叫做重连通图。 在重连通图上, 任何一对顶点之间至少存在有 两条路径, 在删去某个顶点及与该顶点相关联 的边时, 也不破坏图的连通性。

17 dfn 顶点的深度优先数，标明进行深度优先搜索时各顶点访问的次序。
一个连通图G如果不是重连通图，那么它可以包括几个重连通分量。 在一个无向连通图G中, 重连通分量可以利用深度优先生成树找到。 dfn 顶点的深度优先数，标明进行深度优先搜索时各顶点访问的次序。 如果在深度优先生成树中，顶点 u 是顶点 v 的祖先, 则有dfn[u] < dfn[v]。 深度优先生成树的根是关节点的充要条件是它至少有两个子女。 其它顶点 u 是关节点的充要条件是它至少有一个子女 w, 从 w 出发, 不能通过 w、w 的子孙及一条回边所组成的路径到达 u 的祖先。

18