#includeusing namespace std; #include #include #define MVNum 100 #define OK 1 #define ERROR 0 int indegree[100]; int d[100]; //定义拓扑排序数组 typedef struct edge { int adjvex; struct edge*nextarc; }edge; typedef struct graph { char data; edge*firstarc; }graph,graphlist[100]; typedef struct graphadj{ int numvex,numarc; graphlist adjlist; }graphadj; void creategraph(graphadj*g); void printfgraph(graphadj*g); void find(graphadj*g,int indegree[]); void toposort(graphadj*g); int main() { graphadj*g; g=(graphadj*)malloc(sizeof(graphadj)); creategraph(g); printfgraph(g); toposort(g); } void find(graphadj*g,int indegree[]) { for(int i=0;i numvex;i++) { indegree[i]=0; } for(int i=0;i numvex;i++) { edge*p; p=g->adjlist[i].firstarc; while(p) { indegree[p->adjvex]++; p=p->nextarc; } } } void toposort(graphadj*g) { find(g,indegree); int stack[100]; int top=-1; for(int i=0;i numvex;i++) { if(indegree[i]==0) { stack[++top]=i; } } int count=0; while(top!=-1) { int index; index=stack[top--]; cout< adjlist[index].data; ++count; edge *p; for(p=g->adjlist[index].firstarc;p;p=p->nextarc) { int k=p->adjvex; indegree[k]--; if(indegree[k]==0) { stack[++top]=k; } } } if(count numvex) { cout<<"该图有回路"; return; } } void creategraph(graphadj*g) { edge*p; int i; int vi,vj; cout<<"请输入图的顶点树和边数:"< >g->numvex>>g->numarc; for(i=0;i numvex;i++) { cin>>g->adjlist[i].data; } for(i=0;i numvex;i++) { g->adjlist[i].firstarc=NULL; } for(i=0;i numarc;i++) { cout<<"请输入vi,vj边的顶点"< >vi>>vj; p=(edge*)malloc(sizeof(edge)); p->adjvex=vj; p->nextarc=g->adjlist[vi].firstarc; g->adjlist[vi].firstarc=p; } } void printfgraph(graphadj*g) { int i,j,k; edge *p; cout<<"以下为邻接表的输出:"< numvex;i++) { cout< adjlist[i].data<<" "; p=g->adjlist[i].firstarc; while(p) { cout< adjvex<<" "; p=p->nextarc; } cout< 可直接测试



