1 #include <iostream>  2 #include <queue>  3 #include <string>  4 using namespace std;  5   6 //表结点  7 typedef struct ArcNode{  8     int adjvex;//该弧所指向的顶点的位置   9     ArcNode *nextarc; 10 }ArcNode; 11  12 //头结点 13 typedef struct VNode{ 14     string data;//顶点信息 15     ArcNode *firstarc;//第一个表结点的地址，指向第一条依附该顶点的弧的指针 16 }VNode, AdjList[10]; 17  18 typedef struct ALGraph{ 19     AdjList vertices; 20     int vexnum, arcnum; 21 }ALGraph; 22  23 int LocateVex(ALGraph G, string u)//返回顶点u在图中的位置 24 { 25     for(int i=0; i<G.vexnum; i++) 26         if(G.vertices[i].data=http://www.mamicode.com/=u) 27             return i; 28     return -1; 29 } 30  31 void CreateDG(ALGraph &G)//构造有向图 32 { 33     string v1, v2; 34     int i, j, k; 35     cout<<"请输入顶点数和边数："; 36     cin>>G.vexnum>>G.arcnum; 37  38     cout<<"请输入顶点："; 39     for(i=0; i<G.vexnum; i++) 40     { 41         cin>>G.vertices[i].data; 42         G.vertices[i].firstarc=NULL; 43     } 44  45     cout<<"请输入边："<<endl; 46     for(k=0; k<G.arcnum; k++) 47     { 48         cin>>v1>>v2; 49         i=LocateVex(G, v1); 50         j=LocateVex(G, v2); 51  52         ArcNode* arc=new ArcNode; 53         arc->adjvex=j; 54         arc->nextarc=G.vertices[i].firstarc; 55         G.vertices[i].firstarc=arc; 56     } 57 } 58  59 void FindIndegree(ALGraph G, int indegree[])//求顶点的入度 60 { 61     for(int i=0; i<G.vexnum; i++) 62         indegree[i]=0; 63  64     for(i=0; i<G.vexnum; i++) 65     { 66         ArcNode *p=G.vertices[i].firstarc; 67         while(p) 68         { 69             indegree[p->adjvex]++; 70             p=p->nextarc; 71         } 72     } 73 } 74  75 void TopologicalSort(ALGraph G)//拓扑排序 76 { 77     queue<int> q; 78     int indegree[10]={0};//入度数组 79     int count=0;//计数，计入队数 80  81     FindIndegree(G, indegree); 82  83     for(int i=0; i<G.vexnum; i++)//入度为0的顶点入队 84         if(0==indegree[i]) 85             q.push(i); 86      87     while(!q.empty()) 88     { 89         int v=q.front(); 90         q.pop(); 91         count++; 92         cout<<G.vertices[v].data<<" "; 93         ArcNode *p=G.vertices[v].firstarc; 94         while(p)//出队后，每个邻接点入度减1 95         { 96             if(!(--indegree[p->adjvex])) 97                     q.push(p->adjvex);//入度为0的顶点入队 98             p=p->nextarc; 99 100         }101     }102 103     if(count<G.vexnum)//由此判断有向图是否有回路104         cout<<"该有向图有回路"<<endl;105 }106 107 void main()108 {109     ALGraph G;110     CreateDG(G);111 112     cout<<"拓扑排序：";113     TopologicalSort(G);114     cout<<endl;115 116 117 118 }