文档介绍：图的拓扑排序操作一、实验内容题目:实现下图的拓扑排序。1               23        4             5  二、目的与要求(一)目的1、了解拓扑排序的方法及其在工程建设中的实际意义。2、掌握拓扑排序的算法,了解拓扑排序的有向图的数据结构。(二)要求用C语言编写程序,实现图的拓扑排序操作。三、设计思想首先对有向图,我们采取邻接表作为数据结构。且将表头指针改为头结点,其数据域存放该结点的入度,入度设为零的结点即没有前趋。在建立邻接表输入之前,表头向量的每个结点的初始状态为数据域VEX(入度)为零,指针域NXET为空,每输入一条弧<J,K>建立链表的一个结点,同时令k的入度加1,因此在输入结束时,表头的两个域分别表示顶点的入度和指向链表的第一个结点指针。在拓扑排序的过程之中,输入入度为零(即没有前趋)的顶点,同时将该顶点的直接后继的入度减1。(1)、查邻接表中入度为零的顶点,并进栈。(2)、当栈为空时,进行拓扑排序。(a)、退栈,输出栈顶元素V。(b)、在邻接表中查找Vj的直接后继Vk,将Vk的入度减一,并令入度减至零的顶点进栈。(3)、若栈空时输出的顶点数不是N个则说明有向回路,否则拓扑排序结束。为建立存放入度为零的顶点的栈,不需要另分配存储单元,即可借入入度为零的数据域。一方面,入度为零的顶点序号即为表头结点的序号,另一方面,借用入度为零的数据域存放带链栈的指针域(下一个入度的顶点号)。四、具体算法设计#include<iostream>#include<cmath>#include<cstdio>#include<algorithm>#include<stack>usingnamespacestd;#defineMAX9999stack<int>mystack;intindegree[MAX];structnode{intadjvex;node*next;}adj[MAX];intCreate(nodeadj[],intn,intm)//邻接表建表函数,n代表定点数,m代表边数{inti;node*p;for(i=0;i<=n-1;i++){adj[i].adjvex=i;adj[i].next=NULL;}for(i=0;i<=m-1;i++){cout<<"请输入第"<<i<<"条边:";intu,v;cin>>u>>v;p=newnode;p->adjvex=v;p->next=adj[u].next;adj[u].next=p;}return1;}voidprint(intn)//邻接表打印函数{inti;node*p;for(i=0;i<=n-1;i++){p=&adj[i];while(p!=NULL){cout<<p->adjvex<<'';p=p->next;}cout<<endl;}}voidtopsort(nodeadj[],intn){inti;node*p;memset(indegree,0,sizeof(indegree));for(i=0;i<=n-1;i++){p