#include#include#includeusing namespace std;#define MAX_VERTEX_NUM 20#define STACK_INIT_SIZE 100#define STACKINCREAMENT 10#define OK 1#define ERROR 0#define OVERFLOW -1#define Maxname 20typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;int dut;ArcNode;typedef struct VNodeint indegree;char data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum, arcnum;ALGraph;typedef structchar *base;char *top;int stacksize;SqStack;int InitStack(SqStack &S)S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;int StackEmpty(SqStack S)if(S.top=S.base)return ERROR;elsereturn OK;int Push(SqStack &S,int e)if(S.top-S.base=S.stacksize)S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(char);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREAMENT;*S.top+=e;return OK;int Pop(SqStack &S,int &e)if(S.top=S.base)return ERROR;e=*-S.top;return e;int veMaxname,vlMaxname;int CreatGraph(ALGraph &G)int i,j;int v1,v2;ArcNode *q;printf(请输入顶点个数：n);scanf(%d,&G.vexnum);for(i=0;iG.vexnum;i+)G.verticesi.indegree=0;G.verticesi.firstarc=NULL;printf(请分别输入顶点：n);for(i=0;iG.vexnum;i+)cout第iG.verticesi.data;printf(请输入边数：n);scanf(%d,&G.arcnum);printf(请分别输入边的信息：n);for(j=0;jdut);G.verticesv2.indegree+;q-nextarc=NULL;q-adjvex=v2;q-nextarc=G.verticesv1.firstarc;G.verticesv1.firstarc=q;for(i=0;iG.vexnum;i+)printf(第%d个顶点的入度为%dn,i,G.verticesi.indegree);printf(n);return OK;int TopologicalOlder(ALGraph G,SqStack &T)int i,k,count,j;SqStack S;ArcNode *p;InitStack(S);for(i=0;inextarc)k=p-adjvex;if(-G.verticesk.indegree=0)Push(S,k);if(vej+p-dutvek)vek=vej+p-dut;if(countG.vexnum)return ERROR;else return OK;int CtrticalPath(ALGraph G,SqStack &T)int i,j,k;ArcNode *p;if(!TopologicalOlder(G,T)return ERROR;for(i=0;inextarc)k=p-adjvex;if(vlk-p-dutdut;for(j=0;jnextarc)k=p-adjvex;int ee=vej;int el=vlk-p-dut;char tag=(ee=el)?*: ;printf(%3d%3d%3d%3d%3d%2cn,j,k,p-dut,ee,el,tag);void main() SqStack T;InitStack(T);ALGraph H;CreatGraph(H);TopologicalOlder(H,T);CtrticalPath(H,T);system(pause);