判断有向图是否存在回路—拓扑排序

#include <iostream>
#include <string>
#include <queue>
using namespace std;
typedef struct Edgenode
{
int adjvex;
struct Edgenode *next;
}Edgenode;
typedef struct Vertexnode
{
string data;
Edgenode *firstedge;
}Vertexnode,Adjlist[10];
typedef struct Graph
{
Adjlist vertex_node;
int num_vertex;
int num_edge;
}Graph;
int get_location(Graph g, string s)
{
int i;
for(i=0;i<g.num_vertex;i++)
{
if(s == g.vertex_node[i].data)
return i;
}
return -1;
}
void create_graph(Graph &g)//创建有向图
{
int i,j,k;
string s1,s2;
cout<<"请输入顶点数和边数:";
cin>>g.num_vertex>>g.num_edge;
cout<<"请输入顶点:";
for(i=0;i<g.num_vertex;i++)
{
cin>>g.vertex_node[i].data;
g.vertex_node[i].firstedge = NULL;
}
cout<<"请输入边:"<<endl;
for(k=0;k<g.num_edge;k++)
{
cin>>s1>>s2;
i = get_location(g,s1);
j = get_location(g,s2);
Edgenode *p = new Edgenode();
p->adjvex = j;
p->next = g.vertex_node[i].firstedge;
g.vertex_node[i].firstedge = p;
}
}
void print_graph(Graph g)//打印邻接表
{
cout<<"邻接表如下:"<<endl;
int i;
for(i=0;i<g.num_vertex;i++)
{
cout<<g.vertex_node[i].data;
Edgenode *p = g.vertex_node[i].firstedge;
while(p)
{
cout<<"->"<<g.vertex_node[p->adjvex].data;
p = p->next;
}
cout<<endl;
}
}
void find_indegree(Graph g, int indegree[])//计算每个顶点的入度
{
int i;
for(i=0;i<g.num_vertex;i++)
indegree[i]=0;
for(i=0;i<g.num_vertex;i++)
{
Edgenode *p = g.vertex_node[i].firstedge;
while(p)
{
indegree[p->adjvex]++;
p=p->next;
}
}
}
void topologicalsort(Graph g)//拓扑排序
{
int indegree[10];//入度
int count = 0;//计数
find_indegree(g,indegree);
int i;
queue<int> q;
for(i=0;i<g.num_vertex;i++)//把度为0的顶点入队
{
if(indegree[i]==0)
q.push(i);
}
while(!q.empty())
{
int k = q.front();
q.pop();
cout<<g.vertex_node[k].data<<" ";
count++;
Edgenode *p = g.vertex_node[k].firstedge;
while(p)
{
if(--indegree[p->adjvex]==0)//将度为0的顶点的邻接顶点入度减1，如果变为0则将其入队
q.push(p->adjvex);
p=p->next;
}
}
cout<<endl;
if(count != g.num_vertex)//如果最终计数值和顶点数不相等，说明有的顶点入度没有变为0，存在环路
cout<<"有向图存在环路!"<<endl;
}
int main()
{
Graph g;
create_graph(g);
print_graph(g);
cout<<"拓扑排序:"<<endl;
topologicalsort(g);
return 0;
}

测试用例一：

测试用例二：

参考：http://blog.csdn.net/cxllyg/article/details/7603157

最后

以上就是坚定黑米为你收集整理的判断有向图是否存在回路—拓扑排序的全部内容，希望文章能够帮你解决判断有向图是否存在回路—拓扑排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。