实现拓扑排序：
见代码：
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; #define MAXVNUM 10 //顶点最大个数 #define MAX 20 typedef struct Node { int adjvex; struct Node *nextarc; int weight; //边的权 }ArcNode; //表结点 #define VertexType int //顶点元素类型 typedef struct { int outdegree,indegree;//顶点的度，入度 int vetex; VertexType data; ArcNode *firstarc; }VNode/*头结点*/; typedef struct{ VNode vertices[MAXVNUM]; int vexnum,arcnum;//顶点的实际数，边的实际数 }ALGraph; void CreatAdjList( ALGraph &G ) //建立有向图的邻接表存储结构 { int n,m=0,i,j; cout<<"输入顶点个数"<<endl; scanf("%d",&n); //输入顶点个数 cout<<"输入顶点信息\n"; for ( i=1;i<=n;i++) //输入顶点信息 { scanf("%d",&G.vertices[i].vetex); G.vertices[i].firstarc=NULL; } cout<<"输入弧(0 0表示输入停止)\n"; scanf("%d%d",&i,&j); //输入弧 while(i!=0 && j!=0) //两顶点之一为0表示结 { ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i]. firstarc=p; m++; //弧的个数加1 cout<<"输入弧(0 0表示输入停止)\n"; scanf("%d%d",&i,&j); } G.vexnum=n; G.arcnum=m; ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode)); for(i=1;i<=G.vexnum;i++) ///初始化入度出度 { G.vertices[i].indegree=G.vertices[i].outdegree=0; } for(i=1;i<=G.vexnum;i++) ///计算入度出度 { p=G.vertices[i].firstarc; while(p!=NULL) { G.vertices[p->adjvex].indegree++; G.vertices[i].outdegree++; p=p->nextarc; } } } int visited[MAXVNUM] ;// 访问标志数组 int GraphFirstAdj(ALGraph g,int v)//得到v的第一个邻结点 { if(g.vertices[v].firstarc!=NULL) return g.vertices[v].firstarc->adjvex; else return 0; } int GraphNextAdj(ALGraph g,int v,int w)//返回v的（相对于w的）下一个邻接点，若w是v的最后一个邻接点，则返回0 { ArcNode *p= (ArcNode*)malloc(sizeof(ArcNode)); p=g.vertices[v].firstarc; while(p) { if(p->adjvex==w&&p->nextarc!=NULL) return p->nextarc->adjvex; p=p->nextarc; } return 0; } void DFS(ALGraph G, int v) { // 从 顶点v出发递归地深度优先遍历图 G cout<<G.vertices[v].vetex<<endl;visited[v]=1; // 访问v顶点（输出v） for(int w=GraphFirstAdj(G, v); w ; w=GraphNextAdj(G,v,w)) if(!visited[w]) DFS(G, w); } void DFSTraverse(ALGraph G) //深度优先遍历图G { int v; for(v=1;v<G.vexnum;v++) visited[v]=0; // 初始访问数组置未访问标志 for(v=1;v<G.vexnum;v++) if(!visited[v])DFS(G,v); // 对未访问过的顶点调用 DFS } void PrintA(ALGraph G) ///输出邻接表 { int i; ArcNode *p; printf("\n***输出邻接表:***\n"); for(i=1;i<=G.vexnum;i++) { p=G.vertices[i].firstarc; printf("%d",G.vertices[i].vetex); while(p!=NULL) { printf(" -> %d",p->adjvex); p=p->nextarc; } printf("\n"); } printf("\n"); } void PrintDegree(ALGraph A) ///顶点的度 { int i; for(i=1;i<=A.vexnum;i++) { printf("顶点 - 的入度是: - 出度是： - \n",i,A.vertices[i].indegree,A.vertices[i].outdegree); } printf("\n"); } void PrintTuopu(ALGraph A) ///计算拓扑序列 { int t[MAXVNUM][2]; int flag=1,i,j; ArcNode *p=NULL; memset(t,0,sizeof(t)); if(p==NULL)printf("***输出拓扑序列***\n"); for(i=1;i<=A.vexnum;i++) { t[i][0]=A.vertices[i].indegree; t[i][1]=A.vertices[i].outdegree; } for(i=1;i<=A.vexnum&&flag==1;i++) { flag==0; for(j=1;j<=A.vexnum;j++) { if(t[j][0]==0) { t[j][0]=-1; flag==1; break; } } if(flag==1) { p=A.vertices[j].firstarc; printf("%d ",A.vertices[j].vetex); while(p!=NULL) { t[p->adjvex][0]--; p=p->nextarc; } } else { printf("此图有环\n"); return; } } printf("\n"); } int main() { ALGraph G; CreatAdjList(G); PrintA(G); PrintDegree(G); cout<<"\n深度优先遍历\n"; DFSTraverse(G); printf("拓扑序\n"); PrintTuopu(G); return 0; }