拓扑算法算法的实现

1、韩山师范学院实验题目：拓扑排序算法实现班级：2015级软工班作者：黄俊聪#includeusing namespace std;#define MVNum 100/最大顶点数 #define OK 1#define ERROR 0typedef int Status;typedef string VerTexType;typedef int OtherInfo;typedef struct ArcNode/边结点 int adjvex;/该边所指向的顶点的位置 struct ArcNode* nextarc;/指向下一条边的指针 OtherInfo info;/和边相关的信息 ArcNode;

2、 typedef struct VNode/顶点信息 VerTexType data;ArcNode* firstarc;/指向第一条依附该顶点的边的指针 VNode,AdjListMVNum;/Adjlist表示邻接表类型 typedef struct AdjList vertices; int vexnum,arcnum;/图的当前顶点数 ALGraph; typedef struct StackNodeint data;struct StackNode* next;StackNode,*LinkStack;Status InitStack(LinkStack& S)S=NULL;retu

3、rn OK;Status Push(LinkStack& S,int e)LinkStack p;p=new StackNode;p-data=e;p-next=S;S=p;return OK;Status Pop(LinkStack& S,int& e)LinkStack p;p=new StackNode;if(S=NULL)return ERROR;e=S-data;p=S;S=S-next;delete p;return OK;Status StackEmpty(LinkStack S)if(S=NULL)return OK;elsereturn ERROR;Status Locate

4、Vex(ALGraph G,string v) int i; for(int i=0;iG.vexnum;i+) if(G.verticesi.data=v) return i; return ERROR; Status CreateUDG(ALGraph& G) ArcNode* p1,*p2; string v1,v2; int i,j; cout输入总顶点数和总边数：G.vexnumG.arcnum;/输入总顶点数和总边数 cout输入各点，构造表头结点表：endl; for(int i=0;iG.verticesi.data;/输入顶点值 G.verticesi.firstarc=NU

5、LL;/初始化表头结点的指针域为NULL cout输入各边，构造邻接表：endl; for(int k=0;kv1v2;/输入一条边依附的两个顶点 i=LocateVex(G,v1); j=LocateVex(G,v2);/确定v1和v2在G中的位置，即顶点在G.vertices中的序号 p1=new ArcNode;/生成一个新的边结点*p1 p1-adjvex=j;/邻接点序号为j p1-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=p1;/将新结点*p1插入顶点v1的边表头部 return OK;Status FindInDegre

6、e(ALGraph G,int indegree)ArcNode* p;for(int i=0;iG.vexnum;i+)/*入度赋初值0*/indegreei=0;for(int i=0;inextarc)indegreep-adjvex+;/*出度不为零，则该顶点firstarc域指向的弧指向的顶点入度加一*/return OK;Status TopologicalSort(ALGraph G,int topo)LinkStack S; ArcNode* p;int i;int indegreeG.vexnum;FindInDegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;i+)if(!indegreei)Push(S,i);int m=0;string e;while(!StackEmpty(S)Pop(S,i);topom=i;cout拓扑排序的序列为：endl;coutG.verticesi.dataadjvex;-indegreek;if(indegreek=0)Push(S,k);p=p-nextarc;if(mG.vex