拓扑算法算法的实现

《拓扑算法算法的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、韩山师范学院实验题目：拓扑排序算法实现班级：2015级软工班作者：黄俊聪#includeusingnamespacestd;#defineMVNum100//最大顶点数#defineOK1#defineERROR0typedefintStatus;typedefstringVerTexType;typedefintOtherInfo;typedefstructArcNode//边结点{intadjvex;//该边所指向的顶点的位置structArcNode*nextarc;//指向下一条边的指针Othe

2、rInfoinfo;//和边相关的信息}ArcNode;typedefstructVNode//顶点信息{VerTexTypedata;ArcNode*firstarc;//指向第一条依附该顶点的边的指针}VNode,AdjList[MVNum];//Adjlist表示邻接表类型typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数}ALGraph;typedefstructStackNode{intdata;structStackNode*next;}StackN

3、ode,*LinkStack;StatusInitStack(LinkStack&S){S=NULL;returnOK;}StatusPush(LinkStack&S,inte){LinkStackp;p=newStackNode;p->data=e;p->next=S;S=p;returnOK;}StatusPop(LinkStack&S,int&e){LinkStackp;p=newStackNode;if(S==NULL)returnERROR;e=S->data;p=S;S=S->next;deletep;retu

4、rnOK;}StatusStackEmpty(LinkStackS){if(S==NULL)returnOK;elsereturnERROR;}StatusLocateVex(ALGraphG,stringv){inti;for(inti=0;i

5、>G.vexnum>>G.arcnum;//输入总顶点数和总边数cout<<"输入各点，构造表头结点表："<>G.vertices[i].data;//输入顶点值G.vertices[i].firstarc=NULL;//初始化表头结点的指针域为NULL}cout<<"输入各边，构造邻接表："<>v1>>v2;//输入一条边依附的两个

6、顶点i=LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中的位置，即顶点在G.vertices中的序号p1=newArcNode;//生成一个新的边结点*p1p1->adjvex=j;//邻接点序号为jp1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;//将新结点*p1插入顶点v1的边表头部}returnOK;}StatusFindInDegree(ALGraphG,intindegree[]){ArcNode

7、*p;for(inti=0;inextarc)indegree[p->adjvex]++;/*出度不为零，则该顶点firstarc域指向的弧指向的顶点入度加一*/returnOK;}StatusTopologicalSort(ALGraphG,inttopo[]){LinkStackS;ArcNode*p;inti

8、;intindegree[G.vexnum];FindInDegree(G,indegree);InitStack(S);for(i=0;i