给定一个有向图，检查该图中是否包含环。如果给定的图包含至少一个环，你的函数应该返回 true，否则返回 false。例如，下图包含两个环 0->1->2->3->0 和 2->4->2，因此你的函数必须返回 true。
我们已经讨论了基于 DFS 的有向图环检测解决方案。在这篇文章中，我们将讨论基于 BFS 的解决方案。
其核心思想是简单地使用 Kahn 的拓扑排序算法。
步骤 1： 计算图中存在的每个顶点的入度（入边的数量），并将访问节点的计数初始化为 0。
步骤 2： 选取所有入度为 0 的顶点并将它们加入队列（入队操作）。
步骤 3： 从队列中移除一个顶点（出队操作），然后执行以下操作：
- 将访问节点的计数增加 1。
- 将所有其相邻节点的入度减少 1。
- 如果相邻节点的入度减少到 0，则将其加入队列。
步骤 4： 重复步骤 3，直到队列为空。
步骤 5： 如果访问节点的计数不等于图中的节点数，则图中包含环，否则不包含。
如何找到每个节点的入度？
有两种方法可以计算每个顶点的入度：
创建一个入度数组来跟踪：
1) 遍历边数组，只需将目标节点的计数器增加 1。
for each node in Nodes
indegree[node] = 0;
for each edge(src,dest) in Edges
indegree[dest]++
时间复杂度：O(V+E)
2) 遍历每个节点的列表，然后将所有连接到它的节点的入度增加 1。
for each node in Nodes
If (list[node].size()!=0) then
for each dest in list
indegree[dest]++;
时间复杂度：外部 for 循环将执行 V 次，内部 for 循环将执行 E 次，因此总的时间复杂度为 O(V+E)。
该算法的总体时间复杂度为 O(V+E)。
C++
“`cpp
// A C++ program to check if there is a cycle in
// directed graph using BFS.
#include
using namespace std;
// Class to represent a graph
class Graph {
int V; // No. of vertices‘
// Pointer to an array containing adjacency list
list* adj;
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int u, int v);
// Returns true if there is a cycle in the graph
// else false.
bool isCycle();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list[V];
}
void Graph::addEdge(int u, int v)
{
adj[u].push_back(v);
}
// This function returns true if there is a cycle
// in directed graph, else returns false.
bool Graph::isCycle()
{
// Create a vector to store indegrees of all
// vertices. Initialize all indegrees as 0.
vector in_degree(V, 0);
// Traverse adjacency lists to fill indegrees of
// vertices. This step takes O(V+E) time
for (int u = 0; u < V; u++) {
for (auto v : adj[u])
in_degree[v]++;
}
// Create an queue and enqueue all vertices with
// indegree 0
queue q;
for (int i = 0; i < V; i++)
if (in_degree[i] == 0)
q.push(i);
// Initialize count of visited vertices
// 1 For src Node
int cnt = 1;
// Create a vector to store result (A topological
// ordering of the vertices)
vector top_order;
// One by one dequeue vertices from queue and enqueue
// adjacents if indegree of adjacent becomes 0
while (!q.empty()) {
// Extract front of queue (or perform dequeue)
// and add it to topological order
int u = q.front();
q.pop();
toporder.pushback(u);
// Iterate through all its neighbouring nodes
// of dequeued node u and decrease their in-degree
// by 1
list::iterator itr;
for (itr = adj[u].begin(); itr != adj[u].end(); itr++)
// If in-degree becomes zero, add it to queue
if (–in_degree[*itr] == 0)
{
q.push(*itr);
//while we are pushing elements to the queue we will incrementing the cnt
cnt++;
}
}
// Check if there was a cycle
if (cnt != V)
return true;
else
return false;
}
// Driver program to test above functions
int main()
{
// Cre