本文主要是介绍拓扑排序(判断有向图是否有回路),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
#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; }
测试用例一:
测试用例二:
这篇关于拓扑排序(判断有向图是否有回路)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!