数据结构图上课.ppt

弗洛伊德算法 假设Ak(i, j)表示顶点i到j的中间顶点序号不大于k的最短路径长度（k=1，2，?，n），那么对它做n次迭代，第n次迭代后，An(i, j)即为i到j的最短路径值，因为它中间的顶点不受限制，即允许为1～n。算法递推的产生个矩阵序列（逻辑上）：A1, A2,?, An 其始基是A0=g（即图的邻接矩阵）。 设图顶点是从1起编的连续自然数，每条弧i, j都有一个非负的权值cost(i, j)，弧i, j不存在时，cost(i, j)=∞；对任意不同的顶点i和j，定义Ak(i, j)为顶点i到j的中间顶点序号不大于k的最短路径长度，那么 A0(i, j)= cost(i, j) Ak(i, j)=Min{ Ak-1(i, j), Ak-1(i, k)+ Ak-1(k, j)} （k≥1） 本章小结 1. 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。 2. 熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。 在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。 3. 理解应用图的遍历算法求连通图的生成树问题。 4. 理解教科书中讨论的各种图的算法。 Thank You! * * * * * * * * * * * 5.5.2 拓扑排序 检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。 什么叫拓扑排序？ 对有向图进行如下操作：按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列。 例： 可求得拓扑有序序列： {a, b, d, f, c, e, g} 和{a, b, c, d, e, f, g}， 还有其他的序列。 如何进行拓扑排序 1、从有向图中选取一个没有前驱的顶点，并输出之； 2、从有向图中删去此顶点以及所有以它为尾的弧； 重复上述两步，直至图空，或者图不空但找不到没有前驱的顶点为止。 如何进行拓扑排序 c a b h c d g f e a b g h d f e 拓扑序列不唯一 如何进行拓扑排序 在算法中需要用定量的描述替代定性的概念 没有前驱的顶点 = 入度为零的顶点 删除顶点及以它为尾的弧 = 弧头顶点的入度减1 为了方便找到尚未输出的无前驱顶点，可设一个队列(或栈)暂存所有入度为0的顶点。 拓扑排序算法 // 对图g中的各顶点求入度，存入inArr Template class VertexType void FindInDegree( ALGraphVertexType g, int inArr[]) { int i,v; for(i=0; ig.GetNumVertices(); i++) inArr[i]=0; for(i=0; ig.GetNumVertices(); i++){ v=g.GetFirstAdjVex(i); while(v!=-1){ inArr[v]++; v=g.GetNextAdjVex(i,v); } } } 拓扑排序算法（续1） // 拓扑排序。若有向图g中无回路，此函数通过topoArr返回一个顶点序号的拓 //扑序列，并返回true；否则返回false。toppArr存放拓扑次序 templateclass VertexType bool TopologicalSort(ALGraphVertexType g, int* topoArr) { queueint q; // 存放度为0的顶点的序号 VertexType vex; int count=0, i, w; int* inDegree=new int[g.GetNumVertices()]; // 存放顶点的入度 FindInDegree(g, inDegree); // 计算所有顶点的入度 fo