グラフ理論：有向グラフのループ検出とループ取得

グラフ理論：有向グラフのループ検出とループの取得#

グラフの関連概念#

頂点#

辺（有向、無向）#

ある頂点に向かう辺が 1 本ある場合、その頂点の入次数は1であると言います；同様に、頂点から出発する辺が 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/)

// 入力: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
// 出力: true

// 入力: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
// 出力: 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

コース間の相互関係は一種のトポロジー関係です。

トポロジー列とは何ですか？トポロジー列をどのように探しますか？

任意のコースの前提条件がわかっている場合、学生に大学 4 年間のコース表を作成するように頼むと、そのコース表に含まれるコースの順序は実際にはトポロジー列です。

具体的な方法：有向グラフの中で、入次数が0の頂点を見つけ、それらの頂点をキューに入れ、順次これらの頂点とその関連する辺を削除します。この手順を繰り返すことで、トポロジー列を得ることができます。


// トポロジカルソート

// 入力: [[1,0],[2,0],[3,1],[3,2]]
// 出力: [0, 1, 2, 3] または [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つの色を使用してマークするのですか？

実際には剪定に相当し、色が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より大きい頂点に対してもここに到達する可能性があるため、探索中に終点に到達したかどうかを確認する必要があります。
    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;
}

ここには一組のデータがタイムアウトする主な理由は、問題は実際にはループを 1 つ見つけるだけでよく、私の解法はビジネス上のニーズを満たすためにすべてのループを見つけるように拡張したため、理論的には 1 つのループを見つけた時点で終了すれば、AC になるはずです。

1-5

TODO：入次数が1より大きい頂点の存在を完璧に処理できていません。pre2を二次元に変更し、ノードのすべての親ノードを探索する必要があります。~~現在、広範囲探索と深さ優先探索の両方が可能です。~~

~~深さ優先探索を使用するべきです！！~~ それでも正しくありません。広範囲探索も実行可能です。