tuopupaixu.rar_随机拓扑

#include <iostream> using namespace std; #define MAX_VERTEX_NUM 20 typedef struct ArcNode{//图的邻接表的定义 int adjvex; struct ArcNode *nextarc; int info; }ArcNode; typedef struct VNode{ char data; int indegree; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; int LocateVex(ALGraph G,char u) { int i; for (i=0;i<G.vexnum;i++) { if(u==G.vertices[i].data) return i; } if (i==G.vexnum) {printf("Error u!\n");exit(1);} return 0; } ALGraph CreateALGraph_adjlist(ALGraph G){ int i,j,k,w;char v1,v2; ArcNode *p; cout<<"输入图的类型,1-有向,2-无向,G.kind="; cin>>G.kind; cout<<"输入G.vexnum="; cin>>G.vexnum; cout<<"输入G.arcnum="; cin>>G.arcnum; cout<<"输入顶点及其入度"<<endl; for(i=0;i<G.vexnum;i++) { //初始化头结点数组 cin>>G.vertices[i].data; cin>>G.vertices[i].indegree; G.vertices[i].firstarc=NULL; } for(k=0;k<G.arcnum;k++){ cout<<"输入弧（边）v1-v2"<<endl; cin>>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); if(i==j&&G.kind==2) cout<<"无向图顶点没有环，重新输入"<<endl; if(i>=0&&j>=0&&(G.kind==1||i!=j)){ p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=w; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; if(G.kind==2){ p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=i; p->info=w; p->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p; } } else k--; } return G; } int ToplogicalSort(ALGraph G){ ArcNode *p; int k; int top=-1; //入度为零的顶点栈初始化 for (int i=0;i<G.vexnum;++i) if (G.vertices[i].indegree==0){ G.vertices[i].indegree=top; top=i; //入度为零顶点进栈 } int count=0; while (top+1) { i=top; top=G.vertices[top].indegree; cout<< G.vertices[i].data; ++count; for (p=G.vertices[i].firstarc;p;p=p->nextarc) {//扫描该顶点的出边表 k=p->adjvex; //边的另一顶点 G.vertices[k].indegree--; //顶点入度减1 if (G.vertices[k].indegree==0) {G.vertices[k].indegree=top; top=k;}//入度为0入栈 } } if (count<G.vexnum) return -1;//有向环 else return 0; } int main() {ALGraph G; G=CreateALGraph_adjlist(G); cout<<"拓扑排序为"<<endl; ToplogicalSort(G); cout<<endl; return 0; }