拓扑排序（判断有向图是否有回路）

本文主要是介绍拓扑排序（判断有向图是否有回路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <iostream>  
#include <queue>  
#include <string>  
using namespace std;  //表结点  
typedef struct ArcNode{  int adjvex;//该弧所指向的顶点的位置   ArcNode *nextarc;  
}ArcNode;  //头结点  
typedef struct VNode{  string data;//顶点信息  ArcNode *firstarc;//第一个表结点的地址，指向第一条依附该顶点的弧的指针  
}VNode, AdjList[10];  typedef struct ALGraph{  AdjList vertices;  int vexnum, arcnum;  
}ALGraph;  int LocateVex(ALGraph G, string u)//返回顶点u在图中的位置  
{  for(int i=0; i<G.vexnum; i++)  if(G.vertices[i].data==u)  return i;  return -1;  
}  void CreateDG(ALGraph &G)//构造有向图  
{  string v1, v2;  int i, j, k;  cout<<"请输入顶点数和边数：";  cin>>G.vexnum>>G.arcnum;  cout<<"请输入顶点：";  for(i=0; i<G.vexnum; i++)  {  cin>>G.vertices[i].data;  G.vertices[i].firstarc=NULL;  }  cout<<"请输入边："<<endl;  for(k=0; k<G.arcnum; k++)  {  cin>>v1>>v2;  i=LocateVex(G, v1);  j=LocateVex(G, v2);  ArcNode* arc=new ArcNode;  arc->adjvex=j;  arc->nextarc=G.vertices[i].firstarc;  G.vertices[i].firstarc=arc;  }  
}  void FindIndegree(ALGraph G, int indegree[])//求顶点的入度  
{  for(int i=0; i<G.vexnum; i++)  indegree[i]=0;  for(i=0; i<G.vexnum; i++)  {  ArcNode *p=G.vertices[i].firstarc;  while(p)  {  indegree[p->adjvex]++;  p=p->nextarc;  }  }  
}  void TopologicalSort(ALGraph G)//拓扑排序  
{  queue<int> q;  int indegree[10]={0};//入度数组  int count=0;//计数，计入队数  FindIndegree(G, indegree);  for(int i=0; i<G.vexnum; i++)//入度为0的顶点入队  if(0==indegree[i])  q.push(i);  while(!q.empty())  {  int v=q.front();  q.pop();  count++;  cout<<G.vertices[v].data<<" ";  ArcNode *p=G.vertices[v].firstarc;  while(p)//出队后，每个邻接点入度减1  {  if(!(--indegree[p->adjvex]))  q.push(p->adjvex);//入度为0的顶点入队  p=p->nextarc;  }  }  if(count<G.vexnum)//由此判断有向图是否有回路  cout<<"该有向图有回路"<<endl;  
}  void main()  
{  ALGraph G;  CreateDG(G);  cout<<"拓扑排序：";  TopologicalSort(G);  cout<<endl;  }  

测试用例一：

 

 

测试用例二：

这篇关于拓扑排序（判断有向图是否有回路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---