DFS（深さ優先探索）を使ったトポロジカルソートについて

前提

トポロジカルソートの勉強をしています。参照しているサイトは次のものです。

BFSを使った方は理解できますし、実際に期待通りに動くように見えます。一方で、DFSの方で混乱しています。例えば、1のサイトからコピペしてmain()を追加したコードを書きました。

C++
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Edge {
5    int to;
6};
7using Graph = vector<vector<Edge>>;
8
9/* topo_sort(G): グラフG をトポロジカルソート
10    返り値: トポロジカルソートされた頂点番号
11    計算量: O(|E|+|V|)
12 */
13void dfs(const Graph &G, int v, vector<bool> &used, vector<int> &ans) {
14    used[v] = true;
15    for (auto e : G[v]) {
16        if (!used[e.to]) {
17            dfs(G, e.to, used, ans);
18        }
19    }
20    ans.push_back(v);  // 帰りがけにpush_back
21}
22vector<int> topo_sort(const Graph &G) {  // bfs
23    vector<int> ans;
24    int n = (int)G.size();
25    vector<bool> used(n, false);
26    for (int v = 0; v < n; v++) {  // 未探索の頂点ごとにDFS
27        if (!used[v]) dfs(G, v, used, ans);
28    }
29    reverse(ans.begin(), ans.end());  // 逆向きなのでひっくり返す
30    return ans;
31}
32
33int main()
34{
35    Graph graph(2);
36    Edge e;
37
38    e.to = 1;
39    graph[0].push_back(e);
40
41    e.to = 0;
42    graph[1].push_back(e);
43
44    auto ts = topo_sort(graph);
45
46    for( auto i : ts )
47        cout << i << endl;
48}

main()でしているのはノード0が1を、ノード1が0を参照している単純な循環のあるグラフを作っています。これを実行するとトポロジカルソートに成功します。しかし循環があるので本来は失敗するはずです。BFSを使ったものは失敗します。

コードを読んでみると、ノード0でdfs()を始めます。ここでused[0] = trueになります。used[1]はfalseですから、DFSでノード1に入ります。

2回目のDFS（ノード1を見ている）では、ノード0へのエッジがありますが、used[0] = trueですからこれ以上探索はせず、ループを抜けます。その際に、ans.push_back(1)をしてしまいます。

続けて1回目のDFSに戻り、ループを抜け、ans.push_back(0)を実行します。結果的にansには{1, 0}が入り、一見トポロジカルソートが成功したように見えます。

私はいまトポロジカルソートについて色々調べていて、きちんと理解はしていません。理解するためにコードを読んでいますが、これが正しい実装なのか、私が勘違いしているのかわからず、ここで行き詰まっています。直感では、このコードは誤っています（ループを抜けたところで、ans.push_back(v)するのはよくないのではという気がします）が、絶対に間違いであると言い切る自身もありません。間違っているとしたら何をするのが正しいのかもよくわかりません。いくつか見たところ、トポロジカルソートの動作を図示しているものもありますが、トポロジカルソートが可能な例ばかりで、循環のあるグラフでDFSを使ったトポロジカルソートを行った解説をまだ見つけていません。

実現したいこと

ここに実現したいことを箇条書きで書いてください。

このDFS版のトポロジカルソートを正しいものに修正したい
もし、このコードが正しいのであれば、私が何を間違えているか知りたい
（この実装が間違っているとして）正しい実装の情報があれば知りたい

他にいくつかトポロジカルソートについての記述を見ましたが、概ね同じ実装をしているようです。

よろしくお願いします。

行動規範の内容に同意します

回答2件

ベストアンサー

（Teratailを利用するのは初めてなので、不慣れな点もあるかもしれませんがご了承ください。）
以下順を追って説明したいと思います。

1.そもそもこのコードは正しいのか？

　結論から申しますと、このコードは「グラフがDAGという前提のもとでは」正しく動作します。（これは質問者さんのコードのコピペ元である1のサイトの下の方（「閉路のない有向グラフ DAG との関係」の項）にも記載されている事実です。）

　では、何故このような前提が無くともしっかりと動く（＝トポロジカルソートが出来ないグラフである場合は例外処理をしてくれる）コードを記載していないのかというと、次に説明するように管理する変数が増えてしまって多少コードが複雑になってしまうからだと考えられます（とはいっても、そこまで複雑にはなりませんが）。もし予めDAG（＝トポロジカルソート可能なグラフ、次でこれも説明します）であることが分かっているのであれば、わざわざ例外処理のコードも記述する必要はなく、DFSを用いた簡潔なコードだけで済みますからね。

2.トポロジカルソートが可能か否かの判定を実装に組み込む

　まず前提知識として、「グラフGがトポロジカルソート可能　⇔　グラフGはDAGである」という重要な同値関係が成立しております（証明等に関しては本筋から外れるので省略します）。ここで、DAGとは"Directed Acyclic Graph"の略であり、英名の通り有向辺(Directed)からなる閉路のない(Acyclic)グラフ(Graph)のことを指します。

　このような知識のもと、どうすればトポロジカルソートが可能か否かを判定出来るようになるのかを考えてみましょう。上の同値関係より、「トポロジカルソートが不可能　⇔　グラフGはDAGではない」が成立します。すなわち、グラフがDAGかどうかが判定出来れば、トポロジカルソートが可能かどうかも判明することが分かります。
次に、DAGでないグラフはどのような特徴を持つのかを考えてみましょう。前述のDAGの定義より、DAGに当てはまらないようなグラフは、

無向グラフである（undirected）
グラフに閉路（サイクル）が含まれる（Cyclic）

のいずれかの特徴を持つことがわかります。ここで、前者に関しては、無向辺を、辺を結ぶ2頂点に関して両向きに伸びる2つの有向辺に書き換えても問題なく、この場合はこの辺を結ぶ2頂点間で閉路が存在するとみなせることから、後者に含めてよいことが分かります。つまり、DAGではないグラフは「グラフに閉路（サイクル）が含まれる」ようなグラフのことを指すのです。

以上の議論より、トポロジカルソートが可能かどうかは、グラフに閉路（サイクル）が含まれるかどうかを判定すればよいことが分かりました。具体的な判定問題が分かったので、後はこの「サイクル検出」のコードをもとのトポロジカルソートのコードに組み込むだけです。

では、どのようにすればサイクル検出を出来るのか、という話になりますが、これは例えばこのサイトの4-6のように同じくDFSを用いて実装することが出来ます。このサイトからサイクル検出の考え方の要点を引用すると、以下のようになります。（以下このサイトを大元にして回答しております。サイトの筆者さんには感謝致します。）

ある頂点 v から出発した探索が、v から行くことのできる全頂点の探索を終えるよりも先に (すなわち、帰りがけ（＝再帰関数から出るタイミング）の状態になる前に)、v に戻って来てしまう（＝再帰を進めていくと他の頂点から辿り着けてしまう）

すなわち、再帰関数を呼び出したタイミング(配列seenで記録することにします）に加えて、再帰関数内の処理が終わって関数から出るタイミング(配列finishedで記録することにします）も記録する必要性が生じます（質問者さんのコードでは、サイクル検出が不要であることを前提としていたため、これらの片方のみを記録していた感じです）。この時、「再帰関数を呼び出し済み」(seen[v] == true) かつ「再帰関数の処理が終わっていない」(finished[v] == false) の状態で、頂点 v について再帰関数を呼び出したときに、グラフがサイクルを含む（＋その頂点vをサイクルが含む）ことが確定します。

ここまでで考え方は述べたので、後はこれをコードに起こすだけです。実装例は以下のようになります。（質問者さんのコードに少し書き足したものなので、実装方法は色々あると思います。ミスがあったらごめんなさい）

C++
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Edge {
8    int to;
9};
10using Graph = vector<vector<Edge>>;
11
12
13bool DAG = true; //トポロジカルソート出来ないならfalse, 出来るならtrueとする
14
15void dfs(const Graph &G, int v, vector<bool> &seen, vector<bool> &finished, vector<int> &ans) {
16    seen[v] = true; //呼び出したタイミング（「行きがけ順」）で記録
17
18    for (auto e : G[v]) {
19        if (!seen[e.to]) {
20            dfs(G, e.to, seen, finished, ans);
21        }
22
23        //サイクル検出（例外処理）
24        else if(seen[e.to] && !finished[e.to]){
25            DAG = false;
26        }
27    }
28
29    finished[v] = true; //再帰関数の処理が終わったタイミング（「帰りがけ順」）で記録
30    ans.push_back(v);  // 帰りがけにpush_back
31}
32
33vector<int> topo_sort(const Graph &G) { 
34    vector<int> ans;
35    int n = (int)G.size();
36    vector<bool> seen(n, false);
37    vector<bool> finished(n, false);
38    for (int v = 0; v < n; v++) {  
39        // 未探索の頂点ごとにDFS
40        if (!seen[v]) dfs(G, v, seen, finished, ans);
41    }
42    reverse(ans.begin(), ans.end());  // 逆向きなのでひっくり返す
43    return ans;
44}
45
46int main()
47{
48//グラフの入力部分
49    Graph graph(2);
50    Edge e;
51
52    e.to = 1;
53    graph[0].push_back(e);
54
55    e.to = 0;
56    graph[1].push_back(e);
57
58    auto ts = topo_sort(graph);
59
60    //グラフがDAGならトポロジカルソート可能
61    if(DAG){
62        for( auto i : ts )
63            cout << i << endl;
64    }
65    //DAGでないならトポロジカルソート不可能
66    else{
67        cout << "unable to sort" << endl;
68    }
69}

以上では質問者さんのトポロジカルソートのコードに修正を加える部分を焦点として回答しましたが、そもそもDFSを用いたトポロジカルソートの仕組みが分からない等追加で質問がございますようでしたら、遠慮なく聞いてください。

投稿2022/09/24 07:10

marc2825

総合スコア26

Hindenburg

2022/09/24 08:18

非常によく理解できました、ありがとうございます。コードまで修正していただき感謝しています。一方で、色々トポロジカルソートについて調べていて、回答でも書いてくださったようにDAGであることと、トポロジカルソート可能であることは同値であるとあるのに、トポロジカルソートを実行する前にDAGであるか確認しなければならないというのは落とし穴のようにも感じます。BFSを用いたものは判定も同時にできるため、DFS版は学習目的にはいいものの、実用面ではBFSのほうがいいようにも感じます。

marc2825

2022/09/24 08:28

ベストアンサーありがとうございます。確かに、BFSの方がその実装方法から安全である（DAGかどうかの判定を内包、DFSだと再帰が深くなってスタックオーバーフローしてしまうような場合もBFSなら問題ない）ので、BFSの方がしっくり来るようでしたら、トポロジカルソートの実装をBFSで統一しても良いと思います。 DFSでトポロジカルソートを書くメリットとしては、（訪問済みかどうかを記録しつつDFSを各頂点に対して行うだけという実装方法から）コードが簡潔になることが一番にあげられるかと思います。自分はDFS版の方がスラスラ書けるように感じるので、（予めDAGであることが分かっていて、グラフのサイズも大きくないような場合は）DFSで書くようにしておりますが、好みの問題でしょう。質問者さんがおっしゃる通り、再帰関数の練習やDFSとトポロジカルソートの関係性を学べるという点では、教育的な例だとも思います。

行動規範の内容に同意します