当前位置：首页 > news >正文

判断图中是否存在环

news 2024/11/5 19:54:42

判断图中是否存在环：

在图论中，判断一个图是否有环可以根据图的类型（有向图或无向图）采用不同的算法。以下是常见的方法：

1. 判断无向图是否有环

对于无向图，可以使用 深度优先搜索（DFS） 或 并查集

方法一：DFS

在无向图中，使用 DFS 遍历时，如果遇到一个已经访问过的节点且这个节点不是当前节点的父节点，则说明图中存在环。
理解无向图中如何通过 DFS 检测环的关键在于父节点的概念。在无向图中，每条边是双向的，因此在 DFS 遍历时，每个节点的相邻节点中可能会包含刚刚访问过的节点（即父节点）。我们不应将这种情况误判为环。

举例解释：DFS 中遇到已访问节点且不是父节点的情况

假设我们有一个无向图，结构如下：

    1/ \0   2\3

在这个图中，边的连接关系是：

0 - 1
1 - 2
2 - 3
3 - 1 （形成了一个环）

步骤演示

我们从节点 0 开始执行 DFS，以下是每一步的过程：

节点 0：
- 标记 0 为已访问。
- 遍历邻接节点 1（尚未访问），所以递归进入节点 1，并将 0 作为 1 的父节点。
节点 1：
- 标记 1 为已访问。
- 遍历邻接节点 0 和 2。
  - 0 是 1 的父节点，所以继续遍历下一个节点。
  - 2 尚未访问，因此递归进入节点 2，并将 1 作为 2 的父节点。
节点 2：
- 标记 2 为已访问。
- 遍历邻接节点 1 和 3。
  - 1 是 2 的父节点，所以继续遍历下一个节点。
  - 3 尚未访问，因此递归进入节点 3，并将 2 作为 3 的父节点。
节点 3：
- 标记 3 为已访问。
- 遍历邻接节点 2 和 1。
  - 2 是 3 的父节点，所以继续遍历下一个节点。
  - 1 已经访问过，但 不是 3 的父节点，说明在 DFS 中遇到了一个环。

此时，我们可以得出结论：图中存在环。

关键点总结

在无向图中，如果在 DFS 遍历过程中，遇到一个已经访问过的节点 且该节点不是当前节点的父节点，说明存在环。
如果遇到的已访问节点是当前节点的父节点（例如 1 -> 2 -> 1 这种情况），则不算环。

通过这个例子，希望能更直观地理解在无向图中检测环的逻辑。
步骤：

初始化一个 visited 数组，用于记录每个节点是否被访问过。
从每个未访问过的节点开始进行 DFS。
在 DFS 中，如果当前节点的某个邻接节点已经被访问过且不等于当前节点的父节点，则说明图中存在环。

代码示例：

#include<bits/stdc++.h>
using namespace std;// 图的邻接表表示
vector<vector<int>> adjList;
vector<bool> vis;// DFS 函数检测节点node是否有环 
bool dfs(int node, int parent) {vis[node] = true;for (int neighbor : adjList[node]) {if (!vis[neighbor]) {if (dfs(neighbor, node)) {// 递归中发现环return true;}} else if (neighbor != parent) {// 遇到已访问节点且不是父节点，说明有环return true;}}return false;
}// 检查图中是否有环
bool hasCycle(int n) {// 初始化 visited 数组vis.assign(n, false);for (int i = 0; i < n; ++i) {// 由于图可能是非连通的，即图可能由多个不相连的部分组成，因此我们需要从每个未访问的节点开始 DFS 检查，这样可以确保图中每个部分都被检查到。if (!vis[i] && dfs(i, -1)) {// 有环return true;} }// 无环return false;
}int main() {int n = 5;// adjList 将变成一个包含 5 个 vector 的二维结构// adjList = {//	{}, // 节点 0 的邻接节点//	{}, // 节点 1 的邻接节点//	{}, // 节点 2 的邻接节点//	{}, // 节点 3 的邻接节点//	{}  // 节点 4 的邻接节点// };adjList.resize(n);adjList[0].push_back(1);adjList[1].push_back(0);adjList[1].push_back(2);adjList[2].push_back(1);adjList[2].push_back(0);adjList[0].push_back(2);// 形成环adjList[1].push_back(3);adjList[3].push_back(1);if (hasCycle(n)) {cout << "Graph has cycle" << endl;} else {cout << "Graph has no cycle" << endl;	}return 0;
}

方法二：并查集（适合稠密图）

并查集方法的思想是，如果在添加一条边的过程中两个顶点已经属于同一个集合，说明添加该边将形成一个环。

步骤：

初始化并查集，将每个节点初始化为自己的集合。
遍历所有边，检查两个端点是否属于同一个集合。
如果两个端点属于同一个集合，说明有环；否则，将它们合并到同一个集合中。

代码：

#include<bits/stdc++.h>
using namespace std;// 存储每个节点的父节点
vector<int> parent;
// 存储每个节点的秩（用于平衡树结构）每个节点的秩通常表示的是它作为根节点的树的高度（或者说深度）的近似值。
vector<int> myRank;// 初始化并查集，每个节点的父节点指向自己，初始秩为0
void init(int n) {parent.resize(n);myRank.resize(n, 0);for (int i = 0; i < n; ++i) {parent[i] = i;}
}// 查找集合的根节点，带路径压缩
int find(int x) {if (parent[x] != x) {// 路径压缩parent[x] = find(parent[x]);}return parent[x]; 
}// 合并两个集合
bool unionSets(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX == rootY) {// x 和 y 已经在同一集合中，形成环return false;} // 按秩合并if (myRank[rootX] > myRank[rootY]) {parent[rootY] = rootX;} else if (myRank[rootX] < myRank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;myRank[rootX] ++;}return true;
}// 判断图中是否有环
bool hasCycle(int n, const vector<pair<int, int>>& edges) {init(n);for(const auto& edge : edges) {int u = edge.first;int v = edge.second;// 如果 u 和 v 已经在同一集合中，说明图中有环if (!unionSets(u, v)) {return true; }	}return false;
}int main() {int n = 5;vector<pair<int, int>> edges = {// 0-1-2-0 形成环{0, 1}, {1, 2}, {2, 0}, {1, 3}};if (hasCycle(n, edges)) {cout << "Graph has cycle" << endl;} else {cout << "Graph has no cycle" << endl;}return 0;		
}

2. 判断有向图是否有环

对于有向图，可以使用 DFS 和 拓扑排序。

方法一：DFS + 递归栈

在有向图中，DFS 遍历时如果遇到一个已经在递归栈中的节点，说明存在环。

步骤：

初始化 visited 数组和 recStack 数组。visited 用于标记节点是否被访问过，recStack 用于标记当前递归调用栈中的节点。
从每个未访问过的节点开始进行 DFS。
如果当前节点的某个邻接节点在递归栈中，则说明存在环。

代码示例：

#include<bits/stdc++.h>
using namespace std;// 深度优先搜索
bool dfs(int node, const vector<vector<int>>& graph, vector<bool>& vis, vector<bool>& recStack) {if (recStack[node]) {// 检测到环return true;} if (vis[node]) {// 已经访问过，不存在环return false;}// 标记当前节点为已访问和在递归栈中recStack[node] = true;vis[node] = true;// 遍历所有邻接节点for (int neighbor : graph[node]) {// 如果发现环，返回 trueif (dfs(neighbor, graph, vis, recStack)) {return true;}}// 从递归栈中移除当前节点 DFS 遍历完一个节点的所有邻接节点后，这意味着我们不再需要在当前递归路径中保留该节点的信息recStack[node] = false;return false;
}// 判断有向图是否有环
bool hasCycleInDirectedGraph(const vector<vector<int>>& graph, int n) {// vector初始化 vector<Type> vis(size, initialValue);vector<bool> vis(n, false);vector<bool> recStack(n, false);// 从每个未访问的节点开始 DFSfor(int i = 0; i < n; ++i) {if (!vis[i]) {if (dfs(i, graph, vis, recStack)) {// 有环return true;}}}// 无环return false;
}int main() {// 节点数量int n = 5;// 有向图的邻接表表示vector<vector<int>> graph(n);// 添加边graph[0].push_back(1); // {0, 1}graph[1].push_back(2); // {1, 2}graph[2].push_back(0); // {2, 0} (形成环)graph[3].push_back(4); // {3, 4}if (hasCycleInDirectedGraph(graph, n)) {cout << "Graph has cycle" << endl;} else {cout << "Graph has no cycle" << endl;}return 0;
}

例题

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> graph(numCourses);// 构建图和计算入度for (const auto& prereq : prerequisites) {int course = prereq[0];int preCourse = prereq[1];graph[preCourse].push_back(course); // preCourse -> course}// 将所有入度为 0 的节点加入队列return hasCycleInDirectedGraph(graph, numCourses) == false;}// 深度优先搜索bool dfs(int node, const vector<vector<int>>& graph, vector<bool>& vis,vector<bool>& recStack) {if (recStack[node]) {// 检测到环return true;}if (vis[node]) {// 已经访问过，不存在环return false;}// 标记当前节点为已访问和在递归栈中recStack[node] = true;vis[node] = true;// 遍历所有邻接节点for (int neighbor : graph[node]) {// 如果发现环，返回 trueif (dfs(neighbor, graph, vis, recStack)) {return true;}}// 从递归栈中移除当前节点 DFS// 遍历完一个节点的所有邻接节点后，这意味着我们不再需要在当前递归路径中保留该节点的信息recStack[node] = false;return false;}// 判断有向图是否有环bool hasCycleInDirectedGraph(const vector<vector<int>>& graph, int n) {// vector初始化 vector<Type> vis(size, initialValue);vector<bool> vis(n, false);vector<bool> recStack(n, false);// 从每个未访问的节点开始 DFSfor (int i = 0; i < n; ++i) {if (!vis[i]) {if (dfs(i, graph, vis, recStack)) {// 有环return true;}}}// 无环return false;}
};

方法二：拓扑排序（适合 DAG）

如果一个有向图可以完成拓扑排序，则该图无环；如果不能完成拓扑排序，说明有环。

步骤：

计算每个节点的入度。
将入度为 0 的节点加入队列。
从队列中取出节点，减少其邻接节点的入度，并在入度为 0 时将该节点加入队列。
如果最终所有节点都被遍历，则无环；否则有环。

#include<bits/stdc++.h>
using namespace std;// 判断有向图是否有环
bool hasCycleUsingTopologicalSort(const vector<vector<int>>& graph, int n) {// 计算每个节点的入度vector<int> inDegree(n, 0);	for (int i = 0; i < n; ++ i) {for (int neighbor : graph[i]) {inDegree[neighbor] ++;} }// 将所有入度为 0 的节点加入队列queue<int> q;for (int i = 0; i < n; ++ i) {if (inDegree[i] == 0) {q.push(i);}}// 记录已访问的节点数int visCount = 0;// 拓扑排序过程while (!q.empty()) {int node = q.front();q.pop();visCount ++;// 减少邻接节点的入度for (int neighbor : graph[node]) {inDegree[neighbor] --;// 如果入度变为 0，加入队列if (inDegree[neighbor] == 0) {q.push(neighbor);}}}// 如果访问的节点数等于总节点数，则无环 如果不相等，则有环return visCount != n;
}int main() {// 节点数量int n = 5;// 有向图的邻接表表示vector<vector<int>> graph(n);// 添加边graph[0].push_back(1); // {0, 1}graph[1].push_back(2); // {1, 2}graph[2].push_back(0); // {2, 0} (形成环)graph[3].push_back(4); // {3, 4}if (hasCycleUsingTopologicalSort(graph, n)) {cout << "Graph has cycle" << endl;} else {cout << "Graph has no cycle" << endl;}return 0;
}