圖論：有向圖的環路檢測和取環

圖論：有向圖的環路檢測和取環#

圖的相關概念#

頂點#

邊（有向、無向）#

一個頂點如果有一條邊指向它，那我們就說這個頂點的入度為1 ；類似地，從頂點出發，有一條邊我們就說這個頂點的出度為 1

圖的表示#

鄰接矩陣

1-1

假設有 n 個頂點 m 條邊的圖，聲明一個 m * n 的二維數組，G[i][j] = 1 表示 i → j 是連通的

但存在幾個問題：

遍歷元素時，存在的邊和不存在的邊都不得不檢查一遍，導致遍歷效率低。
不能存儲重複的邊。
當頂點數量多時，內存空間開銷會很大。
空間利用率不高。
存儲無向圖時，由於此時矩陣是對稱的，而對稱位置上的成對元素保存的信息是重複的，導致空間利用率不高。

鄰接表

1-2

用一個數組adj存儲以這個點可以到達的所有頂點，例如：adj[i] = [a, b, c, d] ，adj[i] 可以是一個鏈表或者數組

數表中關聯字段 cellValue 的結構實際上也可以看成一種鄰接表 (從一個 id 出發，關聯了一個 id 陣列)： id → reocod → linkfield → cellvalue [id1, id2, id3]

圖的環檢測方法#

並查集#

並查集詳解 -- 圖文解說，簡單易懂 (轉)

Q & A

為什麼需要路徑壓縮？為什麼可以壓縮？

最壞的情況下，查找路徑可能退化成一條鏈，極大影響查找效率；

pre 數組並不用存儲真正的節點之間的關係，它的作用只有一個，判斷任意 2 個節點有沒有一個公共祖先；

壓縮的幾種方式：
1. 按秩合併
2. 邊查找邊合併
什麼情況下說明有環？

將要合併的 2 個節點，它們已經擁有公共祖先的時候，說明可能存在環（注意是可能存在 ）
那什麼情況下有公共祖先但是也沒有環呢？

有向圖的情況，要知道有向圖的邊是有方向的，即使 2 個節點存在公共祖先，也不一定構成環，例如：[ [1,2], [1,3], [2,3] ]

不過下面這道題涉及的只是無向圖，因此不用特別處理。

// [https://leetcode-cn.com/problems/graph-valid-tree/](https://leetcode-cn.com/problems/graph-valid-tree/)

// Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
// Output: true

// Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
// Output: false

const int maxN = 2010;
int pre[maxN];

int find(int x) {
  return x == pre[x] ? x : pre[x] = find(pre[x]); // 路徑壓縮，邊查找邊壓縮
}

void _union(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx != fy) {
    pre[fx] = fy;
  }
}

class Solution {
  public:
    bool validTree(int n, vector<vector<int> >& edges) {
      for (int i = 0; i < n; i++) {
        pre[i] = i;
      }
      for (int i = 0; i < edges.size(); i++) {
        int a = edges[i][0], b = edges[i][1];
        if (find(a) == find(b)) {
          return false;
        }
        _union(a, b);
      }
			// 多個分離的樹也不是一棵合法的樹
      set<int> preSet;
      for (int i = 0; i < n; i++) {
        preSet.insert(find(i));
      }
      return preSet.size() == 1;
    }
};

拓撲排序#

什麼是拓撲關係？

舉個例子，一門課程都有它的先修課程

1-3

用圖的方式表示就是:

Untitled

課程之間的相互關係就是一種拓撲關係。

什麼是拓撲序列，如何尋找拓撲序列？

我們知道了任意一門課程的先修課程，如果此時要你來給學生做一張大學四年的課程表，那麼這種課程表中課程組成的序列實際上就是一個拓撲序列

具體做法：在有向圖中，找出入度為 0 的頂點，將這些頂點放到隊列中，依次刪除這些頂點及其相關的邊，重複上一步，就可以得到一個拓撲序列


// 拓撲排序

// input: [[1,0],[2,0],[3,1],[3,2]]
// output: [0, 1, 2, 3] or [0, 2, 1, 3]

const edges = [[1,0],[2,0],[3,1],[3,2]];

const inDegree = [];
// 求頂點的入度
edges.forEach(edge => {
  const [target, source] = edge;
  inDegree[target]++;
});

// 找出入度為 0 的頂點
let queue = [];
inDegree.forEach((val, index) => {
  if (val === 0) {
    queue.push(index)
  };
});

const res = [];

while (queue.length) {
  const cur = queue.shift();
  res.push(cur);
  edges.forEach(edge => {
    const [target, source] = edge;
    if (source === cur) {
      inDegree[target]--;
			// 新的入度為 0 的頂點，一定在這裡產生
      if (inDegree[target] == 0) {
        queue.push(target);
      }
    }
  })
}

console.log(res)

如果找不到一個入度為 0 的頂點，是否就說明一定存在環？

直覺上是，不過還沒找到證明方法。

如何在檢測環的同時取出環？#

要想取出環，意味著我們需要將整個圖至少遍歷一遍，比較直接的做法是深度優先遍歷

算法講解：https://www.youtube.com/watch?v=rKQaZuoUR4M

Q & A

為什麼要使用 3 種顏色標記節點？

其實相當於剪枝，color 為 2 的節點再也不用訪問了.
pre 數組是幹什麼用的？

記錄節點的父節點，找到環時，從 dfs 最後一個探訪的一個節點出發，依次尋找其父節點，直到形成一個環或者在中途路徑斷開（也就是說這個節點沒有父節點了），到此為止，這個過程就在構造環
複雜度是多少？

假設頂點數量為 V，邊的數量為 E ，每條邊都要走一遍，那麼時間複雜度為 O(V+E) ，空間複雜度為 O(V) (實際上我們需要額外的空間保存環結構，所以最壞情況下佔用空間應該是 cv1+cv2+…+cvv＝2^v）
存在什麼隱患？

圖的層級太深會爆棧

JavaScript 版：

// [https://cses.fi/problemset/task/1678](https://cses.fi/problemset/task/1678)

// const n = 4, m = 5;
// const edges = [[1,3], [2,1], [2,4], [3,2], [3,4]];
//const n = 10, m = 20;
//const edges = [[9,8], [2,9],[7,5], [4,5],[1,5],[3,8],[4,2],[5,4],[6,5],[3,6],[8,10],[10,9],[10,7],[9,3],[7,6],[8,7],[7,3],[8,9],[7,10],[2,1]]
const n = 6, m = 7;
const edges = [[1, 2], [2, 3], [3, 1], [1, 4], [4, 6], [6, 5], [5, 4]];

const pre = Array(n + 1).fill(-1);

const color = Array(n + 1).fill(0);

// 建立鄰接表
const adj = [[], [], [], [], [], [], [], [], []]; // 不知道為什麼，初始化用 Array(n + 1).fill([]) 會報錯
edges.forEach(edge => {
  const [source, target] = edge;
  adj[source].push(target);
});

const cycles = [];

const buildCycle = (start, end) => {
  const cycle = [start];
  for (let cur = end; cur !== start; cur = pre[cur]) {
    cycle.push(cur);
  }
  cycle.push(start);
  cycles.push(cycle.reverse());
}

const dfs = source => {
  color[source] = 1;
  adj[source].forEach(target => {
    if (color[target] === 0) {
			pre[target] = source;
      dfs(target);
    } else if (color[target] === 1) {
      // console.log(target, source)
      buildCycle(target, source);
    }
  });
  color[source] = 2;
}

for (let v = 1; v <= n; v++) {
  if (color[v] === 0) {
    dfs(v);
  }
}

console.log(cycles)

C++ 版：

#include<iostream>
#include<vector>
using namespace std;

const int maxN = 1e5+10;
vector<int> color(maxN, 0) , pre(maxN, 0), adj[maxN];

vector<vector<int> > res;

void build_cycle(int start, int end) {
  vector<int> cycle;
  cycle.push_back(start);
  for (int cur = end; cur != start; cur = pre[cur]) {
    cycle.push_back(cur);
  }
  cycle.push_back(start);

  vector<int> reversedCycle;
  for (int i = cycle.size() - 1; i >= 0; i--) {
    reversedCycle.push_back(cycle[i]);
  }

  res.push_back(reversedCycle);
}

void dfs(int source) {
  color[source] = 1;
  for (int &target: adj[source]) {
    if (color[target] == 0) {
      pre[target] = source;
      dfs(target);
    } else if (color[target] == 1) {
      build_cycle(target, source);
    }
  }
  color[source] = 2;
}

int main() {
  int n, m;
  cin >> n >> m;
  while (m--) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
  }

  for (int i = 1; i <= n; i++) {
    if (color[i] == 0) {
      dfs(i);
    }
  }

  if (res.size() != 0) {
    for (int i = 0; i < res.size(); i++) {
      cout << res[i].size() << endl;
      for (int j = 0; j < res[i].size(); j++) {
        cout << res[i][j] << " ";
      }
      cout << endl;
    }
  } else {
    cout << "IMPOSSIBLE" << endl;
  }

  return 0;
}

並查集也可以部分實現，前面提到，對有向圖，我們可以特殊處理一下，依然拿這個例子：[ [1,2], [1,3], [2,3] ], 我們首先合併[1,2], [2,3]，此時 [1,2,3]已經在一個集合中，再合併[2,3], 進入構建環的邏輯: 3 入隊，再找到 2 的祖先是 1，將 1 入隊，1 的祖先不存在，不構成環，所以可以結束遍歷

#include<iostream>
#include<vector>
#include<cmath>
#include<set>
#include<algorithm>
using namespace std;

const int maxN = 1e5+10;

int pre[maxN];

int pre2[maxN];

vector<vector<int> > res;

// TODO: pre2 這個一維數組並不能處理存在入度大於 1 的頂點的情況，可以改成二維，~~廣搜跑一遍~~，不對應該深度優先
void buildCycle(int start, int end) {
  
  vector<int> cycle;
  cycle.push_back(start);
  for (int cur = end; cur != start; cur = pre2[cur]) {
		// 對於入度大於 1 的頂點，也會走到這裡，所以需要判斷一下查找過程中是不是到盡頭了，到了就直接 return
    if (cur == -1) {
      return;
    }
    cycle.push_back(cur);
  }
  cycle.push_back(start);

  vector<int> reversedCycle;

  for (int i = cycle.size() - 1; i >= 0; i--) {
    reversedCycle.push_back(cycle[i]);
  }

  res.push_back(reversedCycle);
}

int find(int x) {
  // cout << "find" << x << endl;
  return x == pre[x] ? x : pre[x] = find(pre[x]); // 路徑壓縮，邊查找邊壓縮
}

// 5 7
// 1 5
// 1 2
// 1 3
// 3 4
// 4 2
// 2 5
// 4 1

void _union(int x, int y) {
  if (pre2[y] == -1) pre2[y] = x;

  int fx = find(x), fy = find(y);
  if (fx != fy) {
    pre[fx] = fy;
  }
}

int main() {
  int n, m;
  cin >> n >> m;

  for (int i = 0; i <= n; i++) {
    pre[i] = i;
    pre2[i] = -1;
  }

  while (m--) {
    int a, b;
    cin >> a >> b;
    if (find(a) == find(b) ) {
      buildCycle(b, a);
      continue;
    }
    _union(a, b);
  }

  if (res.size() != 0) {
    for (int i = 0; i < res.size(); i++) {
      cout << res[i].size() << endl;
      for (int j = 0; j < res[i].size(); j++) {
        cout << res[i][j] << " ";
      }
      cout << endl;
    }
  } else {
    cout << "IMPOSSIBLE" << endl;
  }

  return 0;
}

這裡有一組數據超時主要是因為，題目其實只要找一個環，我的解法為了滿足業務上可能的需要，擴充了一下，找所有環，理論上改成只找到一個環就結束，應該是可以 AC 的

1-5

TODO：尚不能完美處理存在入度大於 1 的頂點的情況，需要將 pre2 變成二維，再遍歷一個節點的所有父節點，~~目前看廣搜深搜都可~~

~~應該使用深搜！！~~ 還是不對，廣搜其實可以