实训八图的拓扑排序、最短路径构造一、实训目的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: i++)/*邻接链表顶点初始化*/(printf("输入顶点%d的值："，i+1)：scanf("%d"，&adjg.adjlist[i].vertex)：/*输入顶点的值*/fflush(stdin):adjg. adjlist[i]. link = NULL;adjg.adjlist[i].id = O;]printf("Inn");for(i = O; i < adjg.arcnum; i++)(printf（"输入第%d条有向弧的起始顶点和终止顶点（用逗号隔开)：",i + 1);scanf("%d,%d",&s,&d);/*输入弧的起始顶点和终止顶点*/fflush(stdin);while(s < 1 [l s > adjg. vexnum / d < 1 Il 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 i<mg.vexnum; i++)(printf（"输入顶点%d的值："，i+1)：/*输入顶点的值*scanf("%d",&mg.vexs[i]);fflush(stdin):)for(i = O; i<mg.vexnum; i++)/*邻接矩阵初始化*for(j = O; j< mg.vexnum; j++)mg.arcs[i][j] = MAX;for(k = 1; k <= mg.arcnum; k++)printf（"输入第%d条边的起始顶点和终止顶点（用逗号隔开）：",k) ;scanf("%d,%d",&i,&j);/*输入弧的起始顶点和终止顶点*/fflush(stdin):while(i<1lli >mg.vexnum |/j<1 llj>mg.vexnum)【printf（"输入错，重新输入："）；scanf("%d,%d",&i,&j):)printf("输入此边权值：")；/*输入弧上之权值*/scanf("%d", &h);mg. arcs[i - 1][j - 1] = h;]return mg:1