toplogical_sort.rar_topological sorting_拓扑_数据结构 图_数据结构 拓扑排序

#include<iostream> #include<iomanip> using namespace std; //函数结果状态代码 # define TRUE 1 # define FALSE 0 # define OK 1 # define ERROR 0 # define INFEASIBLE -1 # define OVERFLOW -2 #define MAX_VERTEX_NUM 20 //最大顶点数 //用于拓扑排序的图的邻接表的定义 typedef int Status; typedef char VertexType; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; int info; }ArcNode; typedef struct VNode{ VertexType data; int indegree; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum;}ALGraph; //建立邻接表 //定位顶点的函数 int LocateVex(ALGraph G,char u) { int i; for (i=0;i<MAX_VERTEX_NUM;++i) { if(G.vertices[i].data==u) return i; } if (i==G.vexnum) {cin>>"Error u!";exit(1);} return -1; } //建立有向图的邻接表的函数 void CreateALGraph_adjlist(ALGraph &G) { int i,j,k,w; char v1,v2; ArcNode *p; cout<<"Input vexnum & arcnum:"; cin>>G.vexnum>>G.arcnum; cout<<"Input Vertices:"<<endl; cout<<"Input value of note,a string of char:"; for (i=0;i<G.vexnum;i++) { cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; G.vertices[i].indegree=0; } cout<<"Input Arcs(v1,v2 & w):"<<endl; for (k=0;k<G.arcnum;++k) { cin>>v1>>v2>>w; i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info = w; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; G.vertices[j].indegree++; } return; } //拓扑排序算法 Status ToplogicalSort(ALGraph G){ ArcNode *p; int k; // FindIndegree(G,indegree); 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<<setw(2)<<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 ERROR;//有向环 else return OK; } void main(){ ALGraph G; cout<<"下面开始建立图的邻接表!"<<endl; CreateALGraph_adjlist(G); cout<<"下面是该图的拓扑排序!"<<endl; ToplogicalSort(G); cout<<endl; }