数据结构-拓扑排序和最短路径

《数据结构-拓扑排序和最短路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最短路径问题拓扑排序某个源点到其余各点的最短路径每一对顶点之间的最短路径小结和作业拓扑排序一、定义由集合上的一个偏序关系得到集合的全序关系的操作偏序：自反的、反对称的、传递的全序：R是集合X上的偏序，对于集合X中的任何元素x,y，如果都有xRy或者yRx,则称R是全序关系拓扑排序BDACBDAC偏序就是集合中的部分成员可以比较。全序是集合中的任何成员之间都可以比较。偏序全序拓扑排序按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列拓扑排序用顶点表示活动，弧表示活动间的优先关系的有向图。

2、AOV网（ActivityOnVertexNetWork）AOV网中不应该出现有向环：如果存在环，则某项活动以自己为先决条件，拓扑排序BDAC可求得拓扑有序序列：ABCD或ACBDBDAC不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}拓扑排序拓扑排序---方法11、从有向图中选取一个没有前驱的顶点，并输出之;2、从有向图中删去此顶点以及所有以它为尾的弧;3、重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。拓扑排序---方法1acgbdhfebhacdgfe拓扑序列：在算法中需要用定量的描述替代定性的概念没有前驱的顶点入度为零的顶点删除顶点及以它为尾的弧弧头顶点的入度减

3、1拓扑排序---方法1StatusToplogicalSort(ALGraghG){FindInDegree(G,indegree);InitStack(S);for(i=0;i

4、v);++count;printf(v);for(w=FirstAdj(v);w;w=NextAdj(G,v,w)){--indegree(w);//弧头顶点的入度减1if(!indegree[w])Push(S,w);}//for}//while………………}拓扑排序---算法总的时间复杂度：O(n+e)算法分析：拓扑排序---算法拓扑排序---方法2acgbdhfebhacdgfe拓扑序列：对有向无环图利用深度优先搜索进行拓扑排序。拓扑排序---方法2acgbdhfebhacdgfe此图的一个拓扑序列为：acgbdhfe退出DFS函数顺序：efgdcahb拓扑排序---方法2最先退出DFS

5、函数的顶点是出度为零的顶点，为拓扑排序序列中最后一个顶点。因此，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑排序序列。结论：拓扑排序---方法2voidDFS-ToplogicalSort(GraphG,intv){//如何确定vfor(v=0;v

6、v);printf(“%d”,v)}}拓扑排序---方法2voidDFS-T(GraphG,intv){//从顶点v出发，深度优先搜索遍历连通图Gvisited[v]=TRUE;for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){if(!visited[w])DFS-T(G,w);}//对v的尚未访问的邻接顶点w递归调用DFS-TPush(S,v);//顶点v的DFS函数执行完毕}//DFS-T拓扑排序---练习acgbdhfe写出下图的所有的拓扑序列单源点的最短路径V01001010550V1V2V5V460V32030给定带权有向图G和V0，求

7、从V0到其余各顶点的最短路径。Dijkstra算法1、按照路径长度递增的次序产生最短路径源点v1…v2将最短路径的终点命名为V1，次之的终点命名为V2，……Dijkstra算法S={V0}S={V0,V1}S={V0,V1,V2}…….2、用集合S记录下已经求出的顶点Dijkstra算法3、用数组D记录V0到S中每个顶点的最短路径的长度S={V0,V1,V2,…,Vm}D[i]是V0到Vi的长度0