質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.12%
グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

解決済

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

Hindenburg
Hindenburg

総合スコア2

グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

2回答

1リアクション

1クリップ

677閲覧

投稿2022/09/24 03:10

前提

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

  1. https://algo-logic.info/topological-sort
  2. https://qiita.com/drken/items/23a4f604fa3f505dd5ad#4-3-dag-%E3%81%AE%E3%83%88%E3%83%9D%E3%83%AD%E3%82%B8%E3%82%AB%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88

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

C++

#include <bits/stdc++.h> using namespace std; struct Edge { int to; }; using Graph = vector<vector<Edge>>; /* topo_sort(G): グラフG をトポロジカルソート 返り値: トポロジカルソートされた頂点番号 計算量: O(|E|+|V|) */ void dfs(const Graph &G, int v, vector<bool> &used, vector<int> &ans) { used[v] = true; for (auto e : G[v]) { if (!used[e.to]) { dfs(G, e.to, used, ans); } } ans.push_back(v); // 帰りがけにpush_back } vector<int> topo_sort(const Graph &G) { // bfs vector<int> ans; int n = (int)G.size(); vector<bool> used(n, false); for (int v = 0; v < n; v++) { // 未探索の頂点ごとにDFS if (!used[v]) dfs(G, v, used, ans); } reverse(ans.begin(), ans.end()); // 逆向きなのでひっくり返す return ans; } int main() { Graph graph(2); Edge e; e.to = 1; graph[0].push_back(e); e.to = 0; graph[1].push_back(e); auto ts = topo_sort(graph); for( auto i : ts ) cout << i << endl; }

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版のトポロジカルソートを正しいものに修正したい
  • もし、このコードが正しいのであれば、私が何を間違えているか知りたい
  • (この実装が間違っているとして)正しい実装の情報があれば知りたい

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

よろしくお願いします。

ttb👍を押しています

以下のような質問にはリアクションをつけましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.12%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。