1、1第第1111章章 图图数据结构与算法分析2图的遍历许多应用需要对图中的每个结点恰好访问一许多应用需要对图中的每个结点恰好访问一次次.基于图的拓扑结构基于图的拓扑结构,以特定顺序依次访问图中以特定顺序依次访问图中各个顶点是很有用的各个顶点是很有用的.例如例如: 人工智能搜索人工智能搜索 最短路径问题最短路径问题3图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索深度优先搜索广度优先搜索广度优先搜索遍历应用举例遍历应用举例4图的遍历(2)为了保证访问所有顶点为了保证访问所有顶点:void graphTraverse(const Graph*
2、 G) for (v=0; vn(); v+) G-setMark(v, UNVISITED); / Initialize for (v=0; vn(); v+) if (G-getMark(v) = UNVISITED) doTraverse(G, v);5 从图中某个顶点V0 出发，访问此顶点，然后依次从依次从V0的各个未被访问的邻的各个未被访问的邻接点出发深度优先搜索遍历图接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索遍历图连通图的深度优先搜索遍历连通图的深度优先搜索遍历6Vw1SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、S
3、G2 和 SG3 分别为含顶点W1、W2和W3 的子图。访问顶点 V ：for (W1、W2、W3 ) 若该邻接点W未被访问， 则从它出发进行深度优先搜索遍历。w2w3w27从上页的图解可见:1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个 “访问标志”。2. 如何判别V的邻接点是否被访问？8深度优先搜索(2)Cost: (|V| + |E|).9深度优先搜索 DFS(1)/ Depth first searchvoid DFS(Graph* G, int v) PreVisit(G, v); / Take action G-setMark(v, VIS
4、ITED); for (int w=G-first(v); wn(); w = G-next(v,w) if (G-getMark(w) = UNVISITED) DFS(G, w); PostVisit(G, v); / Take action10 首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜索遍历11图的遍历(2)为了保证访问所有顶点为了保证访问所有顶点:void graphTraverse(const Graph* G) for (v=0; vn(); v+) G-
5、setMark(v, UNVISITED); / Initialize for (v=0; vn(); v+) if (G-getMark(v) = UNVISITED) doTraverse(G, v);12abchdekfgF F F F F F F F FT T T T T T T TTach d kfe bgachkfedbg访问标志访问标志: :访问次序访问次序: :例如例如:0 1 2 3 4 5 6 7 813二、广度优先搜索遍历图Vw1w8w3w7w6w2w5w4对连通图，从起始点V到其余各顶点必定存在路径。 其中，V-w1, V-w2, V-w8 的路径长度为1；V-w7,
6、V-w3, V-w5 的路径长度为2；V-w6, V-w4 的路径长度为3。w1Vw2w7w6w3w8w5w414 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问未被访问过的邻接点，之后按这些顶点被访问的先后次按这些顶点被访问的先后次序依次访问它们的邻接点序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。15广度优先搜索 (1)除了用队列代替递归栈外，除了用队列代替递归栈外，BFS的实现与的实现与DFS相似相似. BFS在进一步深入访问
7、其他顶点前，检查起点在进一步深入访问其他顶点前，检查起点的所有邻接点的所有邻接点.16Breadth First Search (3)17Breadth First Search (2)void BFS(Graph* G, int start,Queue*Q) int v, w; Q-enqueue(start); / Initialize Q G-setMark(start, VISITED); while (Q-length() != 0) / Process Q Q-dequeue(v); PreVisit(G, v); / Take action for(w=G-first(v);wn
8、();w=G-next(v,w) if (G-getMark(w) = UNVISITED) G-setMark(w, VISITED); Q-enqueue(w); 18三、遍历应用举例1. 求一条求一条从顶点从顶点 i 到顶点到顶点 s 的的 简单路径简单路径2. 求两个顶点之间的一条求两个顶点之间的一条路径路径 长度最短长度最短的路径的路径191. 求一条求一条从顶点从顶点 i 到顶点到顶点 s 的简单路径的简单路径abchdekfg 求从顶点 b b 到顶点 k k 的一条简单路径。 从顶点 b b 出发进行深度优先搜索遍历。例如例如: : 假设找到的第一个邻接点是a a，则得到的结点
9、访问序列为: b a d h c e k f g。 假设找到的第一个邻接点是c c，则得到的结点访问序列为: b c h d a e k f g，201. 从顶点 i 到顶点 s ,若存在路径，则从顶点 i 出发进行深度优先搜索，必能搜索到顶点 s 。2. 遍历过程中搜索到的顶点不一定是路径上的顶点。结论结论:3. 由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。21void DFSearch( int v, int s, char *PATH) / 从第v个顶点出发递归地深度优先遍历图G， / 求得一条从v到s的简单路径，并记录在PATH中 visitedv = TRUE; / 访
10、问第 v 个顶点 Append(PATH, getVertex(v); / 第v个顶点加入路径 for (w=FirstAdjVex(v); w!=0&!found; w=NextAdjVex(v) ) if (w=s) found = TRUE; Append(PATH, w); else if (!visitedw) DFSearch(w, s, PATH); if (!found) Delete (PATH); / 从路径上删除点 v 222. 求两个顶点之间的一条求两个顶点之间的一条路径路径 长度最短长度最短的路径的路径 若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?23abchdekfg因此，求路径长度最短的路径可以基于广求路径长度最短的路径可以基于广度优先搜索遍历进行度优先搜索遍历进行，但需要修改链队列修改链队列的结点结构及其入队列和出队列的算法的结点结构及其入队列和出队列的算法。深度优先搜索访问顶点的次序次序取决于图的存储结构存储结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。24课后练习课后练习求两个顶点之间的一条求两个顶点之间的一条路径路径 长度最短长度最短的路径的路径 的具体步的具体步骤骤请告诉我（）25要点回顾要点回顾 图型结构是遍历是关键操作26图的最短路径。 课后预习课后预习
