使用 DSU 检测 C++ 图中的环

2025年3月22日 | 阅读21分钟

在本文中，您将通过几个示例了解如何使用DSU在C++中检测图中的环。

Graph

图是一组节点（顶点）和连接节点对的边。图可以是有向的或无向的，并且可以为边分配权重。

环

在无向图中，环是指一个顶点序列，其中第一个和最后一个顶点相同，而其他顶点是唯一的。

在有向图中，环是指一个顶点序列，其中每个顶点都有一条边连接到下一个顶点，最后一个顶点有一条边连接到第一个顶点。

环检测

在各种应用中检测图中的环至关重要，包括确保记录结构的完整性并防止算法中的无限循环。

可以使用各种算法和方法来检测环，每种方法都适用于不同类型的图和场景。

在图（这是图论和计算机技术中的一个基本问题）中检测环是一个基本问题。图中的环是一个从同一顶点开始和结束的顶点和边序列。检测环对于各种程序至关重要，包括确保软件中依赖项的一致性、检测并发系统中的死锁以及识别数据库中的循环引用。

检测图中的环是一个传统的难题，可以使用各种技术来解决。以下是检测图中的环的几种不同方法：

1. 深度优先搜索 (DFS)

深度优先搜索 (DFS) 是一种有效的图遍历算法，它在回溯之前会尽可能深入地探索每个分支。当用于检测图中的环时，DFS 与不相交集并集 (DSU) 结合使用，可以有效地管理顶点集。环检测的关键在于在遍历过程中监视每个顶点的父节点。

在 DFS 和 DSU 的上下文中，该算法维护一个父数组来记录访问过的每个顶点的父顶点。当 DFS 探索图时，它会在必要时进行回溯，并且算法会更新其父信息。环检测的核心是识别出，如果在 DFS 过程中遇到先前访问过的顶点，并且该顶点不是当前顶点的父节点，则会检测到环。

不相交集并集数据结构提高了集合操作的效率，能够快速检查顶点连通性，并在DFS遍历过程中帮助识别环。通过结合 DFS 的表达能力和 DSU 的效率，该算法为检测图中的环提供了一个健壮的解决方案。

这种方法有效地利用了DFS遍历图的性质和DSU管理集合的结构，使其成为网络分析、电路设计等各种应用中检测环的可靠方法。

让我们通过 C++ 中的 DFS 与 DSU 实现来检测环。

#include <iostream>
#include <vector>
using namespace std;
class Graph {
public:
 int vertices;
 vector<vector<int>> adjList;
 Graph(int V) {
 vertices = V;
 adjList.resize(V);
 }
 // Function to add an edge to the graph
 void addEdge(int u, int v) {
 adjList[u].push_back(v);
 adjList[v].push_back(u);
 }
};
class DSU {
public:
 vector<int> parent, rank;
 DSU(int n) {
 parent.resize(n);
 rank.resize(n, 0);
 // Initialize each element as a separate set
 for (int i = 0; i < n; ++i) {
 parent[i] = i;
 }
 }
 // Find operation with path compression
 int find(int x) {
 if (parent[x] != x) {
 parent[x] = find(parent[x]);
 }
 return parent[x];
 }
 // Union operation with rank optimization
 void unionSets(int x, int y) {
 int rootX = find(x);
 int rootY = find(y);
 if (rootX != rootY) {
 if (rank[rootX] < rank[rootY]) {
 parent[rootX] = rootY;
 } else if (rank[rootX] > rank[rootY]) {
 parent[rootY] = roots;
 } else {
 parent[rootX] = rootY;
 rank[rootY]++;
 }
 }
 }
};
bool isCyclicDFS(int v, vector<bool>& visited, vector<bool>& inStack, Graph& graph, DSU& dsu) {
 visited[v] = true;
 inStack[v] = true;
 for (int u : graph.adjList[v]) {
 if (!visited[u]) {
 if (isCyclicDFS(u, visited, inStack, graph, dsu))
 return true;
 } else if (inStack[u] && dsu.find(u) != dsu.find(v)) {
 // If you are in the recursion stack and are not the parent of v, a cycle is detected
 return true;
 }
 }
 inStack[v] = false;
 return false;
}
bool isCyclic(Graph& graph) {
 int V = graph.vertices;
 vector<bool> visited(V, false);
 vector<bool> inStack(V, false);
 DSU dsu(V);
 for (int i = 0; i < V; ++i) {
 if (!visited[i] && isCyclicDFS(i, visited, inStack, graph, dsu))
 return true;
 }
 return false;
}
int main() {
 int vertices = 4;
 Graph graph(vertices);
 // Add edges to the graph
 graph.addEdge(0, 1);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(3, 0);
 if (isCyclic(graph)) {
 cout << "The graph contains a cycle.\n";
 } else {
 cout << "The graph does not contain a cycle.\n";
 }
 return 0;
} 

输出

The graph contains a cycle.

解释

图的表示

Graph 类使用邻接列表来表示无向图。它具有向图中添加边的方法。

DSU (不相交集并集) 实现

DSU 类是不相交集并集数据结构。它具有带路径压缩的 find 操作和带秩优化的 unionSets 操作的方法。

用于环检测的 DFS 函数

isCyclicDFS 函数是一个深度优先搜索 (DFS) 函数。它接受一个顶点 v，跟踪已访问的顶点（visited），并使用堆栈（inStack）在 DFS 遍历期间检测环。
它递归地探索相邻顶点，如果遇到已访问但不是当前顶点父节点的顶点，则表示存在环。

主环检测函数

isCyclic 函数初始化数据结构，包括 DSU，并遍历所有顶点。
对于每个未访问的顶点，它调用isCyclicDFS来执行 DFS 并检查环。如果找到环，则函数返回 true；否则，返回 false。

主函数

在 main 函数中，创建了一个具有四个顶点的示例图，并添加了边以创建环（0 -> 1 -> 2 -> 3 -> 0）。
调用 isCyclic 函数，程序打印图是否包含环。

输出

如果图包含环，则输出将指示图包含环。在此示例中，它将打印“图包含环”。

整体思路是使用 DFS 遍历图，并使用 DSU有效地检查环。DSU 数据结构有助于跟踪顶点集并在遍历期间检测环。该代码优雅地结合了图表示、DSU 实现和 DFS，以有效地检测无向图中的环。

DSU 用于跟踪集合并促进 DFS 遍历期间的环检测。这种模块化且组织良好的代码清晰地理解了使用反向删除算法在图中检测环的过程。

复杂度分析

时间复杂度

DFS 函数 (isCyclicDFS)

DFS 函数访问每个顶点和每条边一次。

DFS 的时间复杂度为O(V + E)，其中 V 是顶点数，E 是边数。

主环检测函数 (isCyclic)

对每个未访问的顶点调用isCyclicDFS，isCyclicDFS 的时间复杂度为O(V + E)。

isCyclic 函数的整体时间复杂度为O(V + E)。

总体复杂度

时间复杂度：O(V + E)

空间复杂度

图的表示

由于邻接列表表示，图的空间复杂度为O(V + E)，其中 V 是顶点数，E 是边数。

DSU 数据结构

DSU 数据结构使用O(V)空间来存储父项和秩数组。

DFS 函数 (isCyclicDFS)

DFS 函数的空间复杂度为O(V)，因为存在递归堆栈（inStack 和 visited 数组）。

主环检测函数 (isCyclic)

isCyclic 函数的整体空间复杂度主要取决于图和 DSU 所需的空间。

总空间复杂度为 O(V + E)。

总体复杂度

空间复杂度：O(V + E)

这些复杂度提供了对算法在时间和空间需求方面的效率的总体理解。时间复杂度与顶点和边的数量成线性关系，使其适用于中等大小的图。空间复杂度也合理，考虑到存储图和 DSU 数据结构的需求。

2. 广度优先搜索 (BFS)

广度优先搜索 (BFS) 是一种图遍历算法，它按级别系统地探索顶点，优先访问邻居，然后再深入更深级别。该算法特别通用，适用于各种与图相关的任务。当应用于无向图中的环检测时，BFS 可以与不相交集并集 (DSU) 数据结构配对，以获得高效可靠的结果。

在环检测的上下文中，BFS 在其探索策略上与深度优先搜索 (DFS) 不同。DFS 使用堆栈来跟踪当前路径中的顶点，而 BFS 则使用队列来系统地按级别探索顶点。这种区别使 BFS 非常适合偏好广度优先探索的应用。

为了使 BFS 能够与 DSU 一起用于环检测，该算法维护DSU结构以有效地管理顶点集及其连通性。当 BFS 遍历图时，它会按级别系统地处理顶点，在探索更深级别之前将邻居入队。DSU 通过有效检查顶点的连通性来帮助确定在两个顶点之间添加边是否会形成环。

该过程包括迭代地出队顶点，探索它们的邻居，并根据连通性信息更新 DSU 结构。如果在任何时候 BFS 遇到一个先前访问过的顶点，而该顶点不是当前顶点的父节点，则会检测到环。DSU 确保这些连通性检查得到有效执行。

BFS 和 DSU 结合用于环检测，提供了与基于 DFS 的方法不同的视角和策略。BFS 中队列的使用提供了系统和分层的探索，使其适用于某些需要广度优先探索的场景。与 DSU 的效率相结合，这种方法成为检测无向图中环的强大工具。

下面将解释如何在 C++ 中使用 BFS 检测带有 DSU 的环。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
public:
 int vertices;
 vector<vector<int>> adjList;
 Graph(int V) {
 vertices = V;
 adjList.resize(V);
 }
 // Function to add an edge to the graph
 void addEdge(int u, int v) {
 adjList[u].push_back(v);
 adjList[v].push_back(u);
 }
};
class DSU {
public:
 vector<int> parent, rank;
 DSU(int n) {
 parent.resize(n);
 rank.resize(n, 0);
 // Initialize each element as a separate set
 for (int i = 0; i < n; ++i) {
 parent[i] = i;
 }
 }
 // Find operation with path compression
 int find(int x) {
 if (parent[x] != x) {
 parent[x] = find(parent[x]);
 }
 return parent[x];
 }
 // Union operation with rank optimization
 void unionSets(int x, int y) {
 int rootX = find(x);
 int rootY = find(y);
 if (rootX != rootY) {
 if (rank[rootX] < rank[rootY]) {
 parent[rootX] = rootY;
 } else if (rank[rootX] > rank[rootY]) {
 parent[rootY] = roots;
 } else {
 parent[rootX] = rootY;
 rank[rootY]++;
 }
 }
 }
};
bool isCyclicBFS(int src, vector<bool>& visited, vector<int>& parent, Graph& graph, DSU& dsu) {
 queue<int> q;
 q.push(src);
 visited[src] = true;
 parent[src] = -1;
 while (!q.empty()) {
 int u = q.front();
 q.pop();
 for (int v : graph.adjList[u]) {
 if (!visited[v]) {
 visited[v] = true;
 q.push(v);
 parent[v] = u;
 } else if (parent[u] != v && dsu.find(u) != dsu.find(v)) {
 // If v is not the parent of you and u and v do not belong to the same set, a cycle is detected
 return true;
 }
 }
 }
 return false;
}
bool isCyclic(Graph& graph) {
 int V = graph.vertices;
 vector<bool> visited(V, false);
 vector<int> parent(V, -1);
 DSU dsu(V);
 for (int i = 0; i < V; ++i) {
 if (!visited[i] && isCyclicBFS(i, visited, parent, graph, dsu))
 return true;
 }
 return false;
}
int main() {
 int vertices = 4;
 Graph graph(vertices);
 // Add edges to the graph
 graph.addEdge(0, 1);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(3, 0);
 if (isCyclic(graph)) {
 cout << "The graph contains a cycle.\n";
 } else {
 cout << "The graph does not contain a cycle.\n";
 }
 return 0; 
}

输出

The graph contains a cycle.

解释

让我们详细分析提供的 C++ 代码，其中使用广度优先搜索 (BFS) 结合不相交集并集 (DSU) 来检测环。

1. 图的表示

Graph 类使用邻接列表表示无向图。

使用addEdge方法将边添加到图中。

2. DSU 实现

DSU 类是不相交集并集数据结构。
它包括带路径压缩的 find 操作和带秩优化的 unionSets 操作的方法。

3. 用于环检测的 BFS 函数 (isCyclicBFS)

此函数从源顶点 (src) 开始执行 BFS 遍历。
它维护一个队列 (q) 进行 BFS 遍历，一个 visited 数组来标记已访问的顶点，以及一个 parent 数组来跟踪遍历期间每个顶点的父节点。
如果遇到一个已访问的顶点，并且它不是当前顶点的父节点，并且这些顶点不属于 DSU 中的同一个集合，则会检测到环。

4. 主环检测函数 (isCyclic)

isCyclic 函数初始化所需的数据结构，包括 DSU。
它遍历所有顶点，为每个未访问的顶点调用isCyclicBFS函数。
如果在任何连通分量中找到环，则该函数返回true；否则，它返回

5. Main 函数

在 main 函数中，创建了一个具有四个顶点的示例图，并添加了边以创建环（0 -> 1 -> 2 -> 3 -> 0）。
调用isCyclic函数，程序打印图是否包含环。

6. 输出

如果图包含环，则输出将指示图包含环。在此示例中，它将打印“图包含环。”
这种方法利用 BFS 进行高效遍历和 DSU 进行环检测，适用于包含环且大小适中的图。

复杂度分析

时间复杂度

BFS 函数 (isCyclicBFS)

BFS 函数探索每个顶点和每条边一次。

BFS 的时间复杂度为O(V + E)，其中 V 是顶点数，E 是边数。

主环检测函数 (isCyclic)

对每个未访问的顶点调用 isCyclicBFS，isCyclicBFS 的时间复杂度为 O(V + E)。

isCyclic 函数的整体时间复杂度为O(V + E)。

总体复杂度

时间复杂度：O(V + E)

空间复杂度

图的表示

图的空间复杂度为O(V + E)，因为有邻接列表表示。

DSU 数据结构

DSU 数据结构使用O(V)空间来存储父项和秩数组。

BFS 函数 (isCyclicBFS)

BFS 函数的空间复杂度为O(V)，因为有队列 (q)、visited 和 parent 数组。

主环检测函数 (isCyclic)

isCyclic 函数的整体空间复杂度主要取决于图和 DSU 所需的空间。

总空间复杂度为O(V + E)。

总体复杂度

空间复杂度：O(V + E)

3. Union-Find (不相交集并集 - DSU)

Union-Find数据结构，通常称为不相交集并集 (DSU)，是一种多功能且高效的工具，用于管理元素集并执行诸如 union 和 find 等操作。此数据结构在各种算法中得到广泛应用，尤其是在与图相关的算法中，包括环检测。

DSU 在有效地管理不相交的顶点集以及确定在两个顶点之间添加边是否会创建无向图中的环方面起着关键作用。DSU 的核心思想是将每个不相交集表示为一棵有根树，其中每个节点指向其父节点。该结构维护有关每个元素的父节点的信息，并针对快速的 union 和 find 操作进行了优化。

DSU 中的 find 操作用于确定特定元素所属集合的代表（根）。在执行此操作时，通常会采用路径压缩来展平树，从而减小树的高度并提高后续 find 操作的效率。

union操作用于合并两个不相交集。为了维护平衡并防止树变得倾斜，采用了秩或大小启发式。这确保了树保持相对平衡，有助于数据结构的整体效率。

在无向图的环检测方面，DSU 在跟踪连通分量和有效确定在两个顶点之间添加边是否会创建环方面表现出色。如果两个顶点属于同一个集合（即具有相同的根），则在它们之间添加边会引入一个环。DSU 在这些操作中的效率使其特别适用于需要快速检查连通性和环形成的场景。

通过在环检测算法中利用 DSU，可以实现简洁性和效率之间的平衡，使其成为需要实时响应能力的场景（例如网络分析、电路设计和各种优化问题）中的首选。

以下是 Union-Find (DSU) 如何用于在 C++ 中检测无向图中的环。

#include <iostream>
#include <vector>
using namespace std;
class Graph {
public:
 int vertices;
 vector<pair<int, int>> edges;
 Graph(int V) {
 vertices = V;
 }
 // Function to add an edge to the graph
 void addEdge(int u, int v) {
 edges.emplace_back(u, v);
 }
};
class DSU {
public:
 vector<int> parent, rank;
 DSU(int n) {
 parent.resize(n);
 rank.resize(n, 1);
 // Initialize each element as a separate set
 for (int i = 0; i < n; ++i) {
 parent[i] = i;
 }
 }
 // Find operation with path compression
 int find(int x) {
 return (parent[x] == x) ? x : (parent[x] = find(parent[x]));
 }
 // Union operation with rank optimization
 bool unionSets(int x, int y) {
 int rootX = find(x);
 int rootY = find(y);
 if (rootX == rootY) {
 // Both vertices are already in the same set, so adding an edge creates a cycle
 return true;
 }
 if (rank[rootX] < rank[rootY]) {
 swap(rootX, rootY);
 }
 parent[rootY] = rootX;
 if (rank[rootX] == rank[rootY]) {
 rank[rootX]++;
 }
 return false;
 }
};
bool isCyclic(Graph& graph) {
 int V = graph.vertices;
 DSU dsu(V);
 for (auto& edge : graph.edges) {
 int u = edge.first;
 int v = edge.second;
 if (dsu.unionSets(u, v)) {
 // A cycle is detected
 return true;
 }
 }
 return false;
}
int main() {
 int vertices = 4;
 Graph graph(vertices);
 // Add edges to the graph
 graph.addEdge(0, 1);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(3, 0);
 if (isCyclic(graph)) {
 cout << "The graph contains a cycle.\n";
 } else {
 cout << "The graph does not contain a cycle.\n";
 }
 return 0; 
}

输出

The graph contains a cycle.

解释

让我们详细分析提供的 C++ 代码，其中使用 Union-Find (Disjoint Set Union - DSU) 来检测无向图中的环。

1. 图的表示

Graph 类使用边列表（edges）表示无向图。
使用addEdge方法将边添加到图中，其中每条边都表示为一对顶点。

2. DSU 实现

DSU 类是不相交集并集数据结构。
它包括带路径压缩的 find 操作和带秩优化的unionSets 操作的方法。

3. Union-Find 操作

Find 操作 (find)

它递归地查找给定元素所属集合的根（代表）。应用路径压缩来展平树。

Union 操作 (unionSets)

它执行两个集合（由它们的根表示）的并集。应用秩优化以保持树的平衡。
如果根相同，则在相应顶点之间添加边会产生环。

4. 环检测函数 (isCyclic)

isCyclic函数初始化 DSU 并遍历图的边。
对于每条边，它使用 DSU 检查添加该边是否会产生环。
如果检测到环，则函数返回 true；否则，返回 false。

5. Main 函数

在 main 函数中，创建了一个具有四个顶点的示例图，并添加了边以创建环（0 -> 1 -> 2 -> 3 -> 0）。
调用 isCyclic 函数，程序打印图是否包含环。

6. 输出

如果图包含环，则输出将指示图包含环。在此示例中，它将打印“图包含环。”
这种方法使用带有路径压缩和秩优化的Union-Find (DSU)数据结构有效地检测无向图中的环。

复杂度分析

时间复杂度

DSU Find 和 Union 操作

带有路径压缩的 find 操作的时间复杂度约为 O(α(V))，其中 α(V) 是反阿克曼函数。该函数增长非常缓慢，对于任何实际的输入大小，都可以认为它在实践中是恒定的。

带有秩优化的 unionSets 操作的平均时间复杂度为O(1)。这是因为秩确保树的高度保持相对较小。

边迭代 (isCyclic Function)

isCyclic 函数中的循环遍历每条边一次，时间复杂度为O(E)，其中 E 是边数。

总体时间复杂度

总体时间复杂度主要取决于 DSU 操作和边迭代。

实际上，总体时间复杂度约为O(V + E)，其中 V 是顶点数，E 是边数。

空间复杂度

图的表示

由于边列表表示，图的空间复杂度为O(E)，其中 E 是边数。每条边都由一对顶点表示。

DSU 数据结构

DSU 数据结构使用O(V)空间来存储父项和秩数组。图中的每个顶点对应 DSU 中的一个元素。

附加变量

函数中使用的其他附加变量，如循环变量和函数参数，在总体分析中的空间需求可以忽略不计。

总体空间复杂度

总体空间复杂度约为O(V + E)，其中 V 是顶点数，E 是边数。

主要的空间使用来自图和 DSU 数据结构。

所提供的算法对于检测无向图中的环非常实用，在时间和空间效率之间取得了良好的平衡。带有路径压缩和秩优化的 Union-Find 操作有助于算法的整体有效性。

4. 拓扑排序（用于有向无环图 - DAG）

拓扑排序是有向无环图（DAG）中顶点的一种系统排列，确保对于每条有向边 (u, v)，顶点 u 在排序中先于顶点 v。这种排序仅限于 DAG，其中不存在循环依赖，使其成为建模和管理任务依赖关系的宝贵工具。

拓扑排序中的每个顶点代表一个任务，而排序本身按尊重其相互依赖性的方式捕获任务的顺序流程。

通过遵循此排序，可以系统地组织和执行任务，避免循环依赖。拓扑排序在项目调度、任务优化和作业排序中具有实际应用，为管理具有相互关联的任务和依赖关系等复杂系统提供了一种结构化方法。

拓扑排序的算法包含两个主要步骤：

基于 DFS 的方法

对图执行深度优先搜索 (DFS) 遍历。

跟踪顶点的完成时间。

使用堆栈根据完成时间存储顶点。

检索拓扑顺序

从堆栈中弹出元素以获得拓扑顺序。

要检测有向图（包括有向无环图 (DAG)）中的环，可以使用深度优先搜索 (DFS) 并在遍历期间检查是否存在后向边。后向边是连接顶点与其在 DFS 树中的祖先的边。如果在DFS遍历期间遇到这样的后向边，则表示图中存在环。

这种方法利用有向边的性质来识别环，因为后向边的存在意味着存在从祖先顶点到当前顶点的路径，从而在有向图中形成环。通过仔细跟踪 DFS 期间的边，此方法可以有效地识别有向图和有向无环图中的环。

下面是带环检测的拓扑排序的 C++ 实现。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
public:
 int vertices;
 vector<vector<int>> adjust;
 Graph(int V) {
 vertices = V;
 adjList.resize(V);
 }
 // Function to add a directed edge to the graph
 void addEdge(int u, int v) {
 adjList[u].push_back(v);
 }
};
vector<int> KahnTopologicalSort(const Graph& graph) {
 int V = graph.vertices;
 vector<int> inDegree(V, 0);
 vector<int> result;
 queue<int> q;
 // Calculate in-degree for each vertex
 for (int u = 0; u < V; ++u) {
 for (int v : graph.adjList[u]) {
 inDegree[v]++;
 }
 }
 // Enqueue nodes with in-degree 0
 for (int u = 0; u < V; ++u) {
 if (inDegree[u] == 0) {
 q.push(u);
 }
 }
 // Process nodes
 while (!q.empty()) {
 int u = q.front();
 q.pop();
 result.push_back(u);
 for (int v : graph.adjList[u]) {
 inDegree[v]--;
 if (inDegree[v] == 0) {
 q.push(v);
 }
 }
 }
 // Check if all nodes are processed
 if (result.size() == V) {
 return result; // Topological ordering
 } else {
 return {}; // Graph contains a cycle
 }
}
int main() {
 int vertices = 6;
 Graph graph(vertices);
 // Add directed edges to the graph
 graph.addEdge(1, 3);
 graph.addEdge(2, 3);
 graph.addEdge(2, 4);
 graph.addEdge(3, 5);
 graph.addEdge(4, 5);
 graph.addEdge(5, 6);
 // Perform topological sorting
 vector<int> result = KahnTopologicalSort(graph);
 // Output the result
 if (result.empty()) {
 cout << "Graph contains a cycle." << endl;
 } else {
 cout << "Topological Ordering: ";
 for (int vertex : result) {
 cout << vertex << " ";
 }
 cout << endl;
 }
 return 0;
}

输出

Topological Ordering: 0 1 2 3 4 5

解释

让我们深入了解提供的 C++ 代码的详细信息，该代码实现了Kahn 算法进行拓扑排序和环检测。

1. Graph 类

Graph 类使用邻接列表（adjust）表示有向图。
该类包含一个构造函数来初始化顶点数（vertices），以及一个（addEdge）方法来向图中添加有向边。

2. Kahn 算法函数 (KahnTopologicalSort)

此函数接受 Graph 对象作为输入，并返回一个表示顶点拓扑顺序的向量，如果检测到环则返回一个空向量。
它初始化了入度（inDegree）、拓扑排序结果（result）和用于处理节点的队列（q）的向量。
通过遍历邻接列表计算每个顶点的入度。入度为 0 的节点将被入队以开始该过程。

3. 处理节点

主循环出队一个节点，处理它（将其附加到结果中），并更新其邻居的入度。
如果邻居的入度变为 0，则将该邻居入队以在下一轮中处理。
此过程一直持续到队列为空。

4. 检查环

处理完所有节点后，函数会检查结果向量中是否存在所有节点。
如果存在，则图是无环的，并且结果向量代表拓扑顺序。
如果不存在，则图包含环，并返回一个空向量。

5. Main 函数

main 函数使用 Graph 类创建了一个示例有向无环图。
它向图中添加了有向边。
调用 KahnTopologicalSort 函数执行拓扑排序。
根据结果，程序会打印拓扑顺序或指示环的存在。

6. 输出示例

如果图包含环，输出将指示图包含环。
如果图是无环的，它将打印拓扑顺序。

Kahn 算法的这种实现是一种简洁有效的方法，可以进行拓扑排序和检测有向无环图中的环。入度的使用简化了具有零入度节点的识别，从而实现了线性时间算法。

复杂度分析

让我们分析一下用于拓扑排序和环检测的 C++ 代码实现 Kahn 算法的时间和空间复杂度。

时间复杂度

计算入度

通过遍历邻接列表计算每个顶点的入度。这需要O(V + E)时间，其中 V 是顶点数，E 是边数。

主循环（处理节点）

在每次迭代中，一个节点被出队，其邻居的入度被更新。这包括遍历邻接列表。

主循环中花费的总时间与边数和顶点数成比例，即O(V + E)。

检查环

最后检查所有节点是否都被处理需要O(V)时间。

总体时间复杂度

O(V + E) - 主要因素是顶点和边的遍历。

空间复杂度

入度数组 (inDegree)

需要O(V)空间来存储每个顶点的入度。

结果向量 (result)

需要O(V)空间来存储拓扑顺序。

队列 (q)

在最坏的情况下，当所有节点的入度都为 0 时，需要O(V)空间。

图表示（邻接列表）

使用邻接列表表示图需要O(V + E)空间。

总体空间复杂度

O(V + E) - 主要因素是入度数组、结果向量和图表示。

Kahn 算法是一种用于有向无环图的拓扑排序和环检测的高效算法。时间和空间复杂度都合理，使其适用于各种应用的实际使用。

结论

深度优先搜索(DFS)深入探索图节点，在路径查找和环检测等任务中非常有用。它在回溯之前会尽可能深入地沿着每个分支进行遍历。另一方面，广度优先搜索(BFS)按级别进行遍历，有助于发现最短路径。
Union-Find（不相交集并集 - DSU）是用于环检测和连接图中组件的高效工具，对于维护连通性信息至关重要。拓扑排序对有向无环图进行排序，为任务调度和依赖关系解析提供了宝贵的见解。这些算法中的每一种都针对特定的图问题，为路径查找、连通性分析和各种应用中的优化等任务提供了通用的工具。

下一主题Find-the-town-judge-in-cpp

使用 DSU 检测 C++ 图中的环

Graph

环

环检测

1. 深度优先搜索 (DFS)

2. 广度优先搜索 (BFS)

3. Union-Find (不相交集并集 - DSU)

4. 拓扑排序（用于有向无环图 - DAG）

基于 DFS 的方法

检索拓扑顺序

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

使用 DSU 检测 C++ 图中的环

Graph

环

环检测

1. 深度优先搜索 (DFS)

2. 广度优先搜索 (BFS)

3. Union-Find (不相交集并集 - DSU)

4. 拓扑排序（用于有向无环图 - DAG）

基于 DFS 的方法

检索拓扑顺序

结论

相关帖子

C++ 中的卡塔德罗姆数

C++ 中的双基回文数

C++ 中的图厄-莫尔斯序列

C++ 2-SAT 问题

C++ 中哈希表和数组的区别

C++ 中的不区分大小写搜索

C++ 中的 Polybius 方形密码

C++ 中的西尔维斯特序列

C++ 中的匈牙利算法

C++ 中检查两个给定字符串的分割子字符串的连接是否构成回文