7.5.2 拓扑排序
假设以有向图表示个工程的施工图或程序的数据流图,每个顶点代表一个活动,弧<vi，vj)表示活动必须先于活动j进行。我们将顶点表示活动、弧表示活动间优先关系的有向无“顶点表示活动的网”,简称"AOV-网"(activity on vertex),图中不允许出现回路。
对于一个AOV-网,若存在满足以下性质的一个线性序列,则这个线性序列称为“拓扑序列”。
①网中的所有顶点都在该序列中。
②若顶点i到顶点Vj存在一条路径,则在线性序列中，Vi一定排在Vj之前。
构造拓扑序列的操作称为“拓扑排序”。实际上,拓扑排序就是离散数学中由某个集合上一个偏序得到该集合上的一个全序的操作。
那么,对于一个AOV-网来说,如何求得拓扑序列呢?其方法如下。
①从有向图中选取一个没有前驱的顶点并输出之。
②从有向图中删去该顶点以及所有以它为尾的弧。
③重复上述两步,直至图空(不存在回路),或者图不空但找不到无前驱的顶点为止(存在 回路)。可见,拓扑排序可以检查有向图中是否存在回路。
相关代码请看配套资源
10-拓扑排序.c
#include<stdio.h> #include<stdlib.h> #include "4-邻接表plus.c" #include "链队列.c" void main(){ AdjList* G=(AdjList*)malloc(sizeof(AdjList)); printf("输入图的类型 "); printf("无向图(1) "); printf("有向图(2) "); printf("无向网(3) "); printf("有向网(4) ："); scanf("%d",&G->t); Create(G); printf("\n"); printf("拓扑排序"); // int indegree[MAXVEX]; // FindID(*G,indegree); // int i; // for(i=1;i<=G->vexnum;i++){ // printf("%d ",indegree[i]); // } TopoSort(*G); printf("\n"); Printf(G); }
运行结果如下
7.5.3关键路径
略
7.5.4最短路径
1.单元最短路径
DIjkstra算法
单源最短路径.c
注意：伪代码不能直接运行
#include<stdio.h> #include<stdlib.h> #include "2-邻接矩阵plus.c" void Dijkstra(AdjMatrix *G,int start,int end,int dist[],int path[][MAXVEX]){ //dist数组记录各条最短路径长度，path数组记录对应路径上的各顶点 int mindist,i,j,k,t=1; for(i=1;i<=G->vexnum;i++){ //初始化 dist[i]=G->arcs[start][i]; if(G->arcs[start][i]!=INFINITY){ path[i][1]=start; } } path[start][0]=1; for(i=2;i<=G->vexnum;i++){ //寻找各条最短路径 mindist=INFINITY; for(j=1;j<=G->vexnum;j++) { //选择最小权值的路径 if(!path[j][0]&&dist[j]<mindist){ k=j; mindist=dist[j]; } } if(mindist==INFINITY) return; path[k][0]=1; for(j=1;j<=G->vexnum;j++){ //修改路径 if(!path[j][0]&&G->arcs[k][j]<INFINITY&&dist[k]+ G->arcs[k][j]<dist[j]){ dist[j]=dist[k]+G->arcs[k][j]; t=1; while(path[k][t]!=0){ //记录最新的最短路径 path[j][t]=path[k][t];//伪代码 t++; } path[j][t]=k; path[j][t+1]=0; } } } } void printPath(AdjMatrix *G,int start,int end,int dist[],int path[][MAXVEX]){ int i,j; printf("从%d到其余顶点\n",start); for(i=1;i<=G->vexnum;i++){ if(i==start){ printf("到本身顶点%d的最短路径长度为0\n",i); }else{ // if(path[i][0]==1){ printf("到顶点%d的最短路径长度为%d\n",i,dist[i]); printf("其路径为："); j=1; while(path[i][j]!=0) { printf("%d ",path[i][j]); j++; } printf("\n"); // }else{ // printf("无路径\n"); // } } } } void main(){ printf("创建\n"); AdjMatrix* G=(AdjMatrix*)malloc(sizeof(AdjMatrix)); printf("输入图的类型 "); printf("无向图(1) "); printf("有向图(2) "); printf("无向网(3) "); printf("有向网(4) ："); scanf("%d",&G->t); Create(G); printf("\n"); int start=1; int end=2; int dist[G->vexnum+1]; int path[G->vexnum+1][MAXVEX]; Dijkstra(G,start,end,dist,path); printPath(G,start,end,dist,path); printf("打印\n"); Printf(G); }
2.每对顶点之间的路径
Floyd算法
6实例分析与实现
略
7算法总结 贪心算法
略
习题
3完成题 1 2 4 6
（1）对于图7-37所示的有向网:
①给出该图对应的邻接矩阵、邻接表和逆邻接表
②判断该图是否为强连通图,并给出其强连通分量
③给出每个顶点的度、人度和出度
④给出从顶点V,开始的深度优先搜索遍历序列和广度优先搜索遍历序列
略
(2)如图7-38所示的无向网,请给出分别按Prim(从顶点V1开始)和Kruskal算法构造的最小生成树并给出构造过程。
略
(4)如图7-40所示的有向网,利用Dijkstra算法求顶点V0到其他各顶点之间的最短路径以及最短路径长度
略
(6)对如图7-42所示的有向图进行拓扑排序,写出可能的3种拓扑序列。
略
4.算法设计题 11
（11)已知有向图以邻接表作为存储结构,编写算法判断该图中是否存在顶点Vi到顶点Vj,的简单路径,并输出该路径上的顶点。
略
