判斷圖中有環的兩種方法及實現
在圖論中，檢測有向圖是否存在環是常見問題。本文將介紹兩種主流方法：DFS三色標記法和拓撲排序（Kahn算法），并提供對應的C++代碼實現。
方法一：DFS三色標記法
核心思想
通過深度優先搜索（DFS）遍歷圖，使用三種顏色標記節點狀態：
- 0（未訪問）：節點尚未被訪問。
- 1（訪問中）：節點正在被訪問，其后續節點仍在遞歸中。
- 2（已訪問）：節點及其所有后代均已處理完畢。
如果在遍歷過程中遇到狀態為1的節點，說明存在環。
時間復雜度
- O(V + E)，其中V為節點數，E為邊數。
C++代碼實現
#include <vector>
using namespace std;bool hasCycleDFS(vector<vector<int>>& graph, int node, vector<int>& color) {color[node] = 1; // 標記為“訪問中”for (int neighbor : graph[node]) {if (color[neighbor] == 0) { // 未訪問的節點if (hasCycleDFS(graph, neighbor, color)) return true;} else if (color[neighbor] == 1) { // 遇到訪問中的節點，存在環return true;}}color[node] = 2; // 標記為“已訪問”return false;
}bool hasCycle(vector<vector<int>>& graph) {int n = graph.size();vector<int> color(n, 0); // 初始化所有節點為未訪問for (int i = 0; i < n; ++i) {if (color[i] == 0 && hasCycleDFS(graph, i, color)) {return true;}}return false;
}
方法二：拓撲排序（Kahn算法）
核心思想
- 統計每個節點的入度（指向該節點的邊數）。
- 將所有入度為0的節點加入隊列。
- 依次處理隊列中的節點，減少其鄰居的入度。若鄰居入度變為0，則加入隊列。
- 若最終處理的節點數不等于總節點數，則存在環。
時間復雜度
- O(V + E)，其中V為節點數，E為邊數。
C++代碼實現
#include <vector>
#include <queue>
using namespace std;bool hasCycleTopo(vector<vector<int>>& graph) {int n = graph.size();vector<int> indegree(n, 0);queue<int> q;// 計算初始入度for (int u = 0; u < n; ++u) {for (int v : graph[u]) {indegree[v]++;}}// 入度為0的節點入隊for (int i = 0; i < n; ++i) {if (indegree[i] == 0) q.push(i);}int cnt = 0; // 記錄處理的節點數while (!q.empty()) {int u = q.front();q.pop();cnt++;for (int v : graph[u]) {if (--indegree[v] == 0) {q.push(v);}}}return cnt != n; // 存在環時cnt < n
}
方法對比與適用場景
| 方法 | 優勢 | 劣勢 | 適用場景 |
|---|---|---|---|
| DFS三色標記法 | 可同時處理其他任務（如路徑記錄） | 遞歸深度可能較大 | 需要深度遍歷信息的場景 |
| 拓撲排序 | 無需遞歸，適合大規模圖 | 僅提供是否存在環的結果 | 只需判斷環或需要拓撲序列的場景 |
完整測試代碼
#include <iostream>
#include <vector>
#include <queue>
using namespace std;// DFS三色標記法
bool hasCycleDFS(vector<vector<int>>& graph, int node, vector<int>& color) {color[node] = 1;for (int v : graph[node]) {if (color[v] == 0) {if (hasCycleDFS(graph, v, color)) return true;} else if (color[v] == 1) {return true;}}color[node] = 2;return false;
}bool hasCycleDFS(vector<vector<int>>& graph) {int n = graph.size();vector<int> color(n, 0);for (int i = 0; i < n; ++i) {if (color[i] == 0 && hasCycleDFS(graph, i, color)) {return true;}}return false;
}// 拓撲排序
bool hasCycleTopo(vector<vector<int>>& graph) {int n = graph.size();vector<int> indegree(n, 0);queue<int> q;for (auto& edges : graph) {for (int v : edges) indegree[v]++;}for (int i = 0; i < n; ++i) {if (indegree[i] == 0) q.push(i);}int cnt = 0;while (!q.empty()) {int u = q.front();q.pop();cnt++;for (int v : graph[u]) {if (--indegree[v] == 0) q.push(v);}}return cnt != n;
}int main() {// 示例：有環圖 0->1->2->0vector<vector<int>> graph = {{1}, {2}, {0}};cout << "DFS三色標記法結果: " << (hasCycleDFS(graph) ? "有環" : "無環") << endl;cout << "拓撲排序結果: " << (hasCycleTopo(graph) ? "有環" : "無環") << endl;return 0;
}
通過這兩種方法，可以高效判斷有向圖中是否存在環。實際應用中，若需要拓撲序列則優先選擇Kahn算法，若需深度遍歷信息則選擇DFS三色標記法。
（本文由deepseek總結生成）
