SWUST OJ#1076(判断给定有向图是否存在回路)

目录

题目

拓扑排序的算法步骤

代码部分

小结

题目

拓扑排序的算法步骤

求出所有顶点的入度，可以附设一个存放各顶点入度的数组indegree[]遍历数组indegree[],如果有顶点的入度为零，便将顶点依次入队或者入栈当栈或者队列不为空时，一直重复下面两个操作

1）进行出栈或者出队的操作，这里假设操作顶点为v

2）将与顶点v邻接的所有顶点的入度减一，如果出现入度为0的顶点，便进行入栈或者入队操作

4. 若此时输出的顶点数小于有向图的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列

代码部分

#include

#include

#include

using namespace std;

int indegree[100], vertexs[100][100];

char Data[100];

int main()

{

queue que;

int m, n, i;

char x, y;

cin >> n >> m;

for (i = 0; i < n; i++) cin >> Data[i]; //存入顶点数据

while (m--)

{

cin >> x >> y;

vertexs[x - 'A'][y - 'A'] = 1;

indegree[y - 'A']++; //计算每个顶点的入度

}

for (i = 0; i < n; i++) if (!indegree[i]) que.push(i); //将入度为零的顶点编号入队

int count = 0; //计算拓扑序列的顶点数

while (!que.empty())

{

int start = que.front();

que.pop();

count++; //相当于输出一个拓扑序列中的一个编号

for (i = 0; i < n; i++)

{

if (vertexs[start][i])

{

vertexs[start][i] = 0;

indegree[i]--;

if (!indegree[i]) que.push(i);

}

}

}

if (count == n) cout << "no"; //存在拓扑排序,即不存在回路

else cout << "yes"; //不存在拓扑排序，即存在回路

return 0;

}

小结

主要代码的解释放在了代码块里面，仅供参考，有问题可以评论区交流，有问必答！！！