图的遍历、拓扑排序、最短路径算法.pdf

 图的遍历、拓扑排序、最短路径算法  图的遍历  定义  图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点 访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作， 图的许多其它操作都是建立在遍历操作的基础之上。  由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：  ① 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。  ② 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考 虑如何选取下一个出发点以访问图中其余的连通分量。  ③ 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。  ④ 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一 个要访问的顶点的问题。  分类  图的遍历可分为四类：  遍历完所有的边而不能有重复，即所谓“一笔画问题”或“欧拉路径”；  遍历完所有的顶点而没有重复，即所谓“哈密尔顿问题”。  遍历完所有的边而可以有重复，即所谓“中国邮递员问题”；  遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。  对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。  第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密尔顿图的性质。   图的遍历  图的遍历有两种遍历方式：深度优先遍历(depth-first search)和广度优先遍历(breadth -first search)。  1.深度优先遍历  基本思想：首先从图中某个顶点v0出发，访问此顶点，然后依次从v0相邻的顶点出发深度 优先遍历，直至图中所有与v0路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中 选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问。可以看出深度优先遍历是一 个递归的过程。  如下图中的一个无向图   其深度优先遍历得到的序列为：  0-1-3-7-4-2-5-6  2.广度优先遍历  基本思想：首先，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访 问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。  如上面图中  其广度优先遍历得到的序列为：  0-1-2-3-4-5-6-7 算法 图的遍历方法目前有深度优先搜索法和广度 （宽度）优先搜索法两种算法。 深度优先搜索法 深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G 的某个顶点v0 出发，访问v0，然 后选择一个与v0 相邻且没被访问过的顶点vi访问，再从vi 出发选择一个与vi相邻且未被访问的顶点vj 进 行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列 中最后一个拥有未被访问的相邻顶点的顶点w，从w 出发按同样的方法向前遍历，直到图中所有顶点都被 访问。其递归算法如下： Booleanvisited[MAX_VERTEX_NUM];//访问标志数组 Status (*VisitFunc)(int v);//VisitFunc 是访问函数，对图的每个顶点调用该函数 void DFSTraverse (Graph G,Status(*Visit)(int v)){ VisitFunc Visit; for(v 0;vG.vexnum;++v) visited[v] FALSE;//访问标志数组初始化 for(v 0;vG.vexnum;++v) if(!visited[v]) DFS(G,v);//对尚未访问的顶点调用DFS } void DFS(Graph G, int v){ //从第v 个顶点出发递归地深度优先遍历图G visited[v] TRUE;VisitFunc(v);//访问第v 个顶点 for(w FirstAdjVex(G,v);w 0;w NextAdjVex(G,v,w)) //FirstAdjVex 返回v 的第一个邻接顶点，若顶点在G 中没有邻接顶点，则返回空 （0）。