塔里木大学：《数据结构》课程教学资源（实验讲义）实训八 图的拓扑排序、最短路径

实训八图的拓扑排序、最短路径构造一、实训目的1、通过实训，掌握图的拓扑排序2、通过实训，掌握最短路径的构造二、实训内容1、练习图的拓扑排序2、练习图的最短路径的构造三、实训前的准备1、复习课本的相关内容2、阅读实训指导书3、准备好相关的程序清单四、实训步骤与方法1、将下面程序补充完整，以完成图的拓扑排序，并输出运行结果（图为P115图7-17)#include#include#include"datastru.h"ADJGRAPHcreat_adjgraphO(/*建立有向图的邻接链表结构*EDGENODE *p;int i, s,d;ADJGRAPH adjg;

adjg.kind = 1;printf（"n\n输入顶点数和边数（用逗号隔开）："）；scanf("%d,%d,&s,&d);fflush(stdin);/*存放顶点数在adjg.vexnum = s;adjg.vexnum中*/adjg.arcnum = d:/*存放边点数在adjg.arcnum中*/printf("\n\n"):for(i = O; i adjg. vexnum / d adjg. vexnum)(printf（"输入错，重新输入："）；scanf("%d,%d",&s,&d):)s --:

d ;/*每条弧对应生成p=malloc(sizeof(EDGENODE)):一个结点*/p->adjvex = d;/*结点插入对应的p->next =adjg.adjlist[s].link;单链表上*/adjg.adjlist[s].link = p;adjg.adjlist[d].id++;]/*弧的终端顶点入度加1*/return adjg:1Jvoidtopsort(ADJGRAPHag)t7main() ADJGRAPH ag:printf（"\n有向图的拓扑排序\n"）；ag = creat_adjgraphO:/*建立有向图的邻接链表结构*topsort(ag) :/*进行拓扑排序*/

printf("InIn"):1运行结果如下：2、对应P116中图7-18的有向图，用邻接矩阵结构存储此图，计算图中从顶点V1出发到其他各项点的最短路径，并输出结果#include"datastru.h"#include#include#define MAX10000MGRAPHcreate_mgraphO(/*建立有向图的邻接矩阵结构*/int i,j,k,h;MGRAPHmg:mg.kind = 3:printf（"nn输入顶点数和边数（用逗号隔开）："）：scanf("%d,%d"，&i,&j);/*存放顶点数在mg.vexnum = i;mg.vexnum中*/mg.arcnum = j:/*存放边点数在mg.arcnum中*/

fflush(stdin):for(i = O img.vexnum |/jmg.vexnum)【printf（"输入错，重新输入："）；scanf("%d,%d",&i,&j):)printf("输入此边权值：")；/*输入弧上之权值*/scanf("%d", &h);mg. arcs[i - 1][j - 1] = h;]return mg:1

main()1MGRAPH mg:int cost [MAXLEN] [MAXLEN] :int path[MAXLEN],s[MAXLEN];int dist[MAXLEN]:inti,j,n,vo,min,u;printf（"\n求有向图单源点最短路径\n"）；mg = create_ mgraphO ;/*建立有向图的邻接矩阵结构*printf（"n\n起始顶点为："）：/*有向图中顶点的编号从1编起*/scanf("%d",&vo);vo --;n = mg.vexnum;for(i =0;i)/*path数组初始化*/

path[i] = vo:]for(i = ; i<n; i++)/*s数组初始化*/s[i] = 0;s[v0] = 1;for(i=o; i<n; i++)/*按最短路径递增算法计算*/1min = MAX :u = vo;for(j=O;j<n;j++)if(s[j] == o && dist[j]< min)(min = dist[j];u = j:)s[u] = 1;/*u顶点是求得最短路径的顶点编号*/for(j= o: j< n:j++)if(s[i] == o && dist[u] + cost[u][j] <dist[j])/*调整dist*/(dist[j] = dist[u] + cost[u][j];path[j] =u:1/*path记录了路径经过的顶点*/1/*打印结果for(i=0:i<n; i++)*/if(s[i] == 1)(u = i:while(u!=vo)

(printf("%d<-",u+1):u = path[u] :]printf("%d ", u + 1);printf("/*有路径d = %d\n", dist[i]);*/1elseprintf("%d<-%dd=MAXin",i+1,vo+1):/*无路径*/printf("In)n");1J运行结果如下：五、实训中出现的问题与解决方