配置済み
配置待ち
調べたエッジ

  • 現在
  • 置ける・訪問中
  • 配置済み
  • 閉路

トポロジカルソートについてもっと見る

トポロジカルソート

靴下の次に靴、基礎の次に壁、ある授業の次にそれを前提とする授業。トポロジカルソートは、一方向のエッジを持つグラフのノードを、どのエッジも前から後ろへ向かう1列に並べます。カーンのアルゴリズムか DFS 法を選んでステップごとに進め、順序が伸びていく様子を見てみましょう。閉路を加えると、なぜそのとき順序がありえないのかもわかります。 「再生」で順序が伸びていく様子を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。エッジはすべて矢印のとおり一方向で、「これはあれより先」という意味だと考えてください。方法を選びます。カーンのアルゴリズムは入ってくるエッジのないノードから置いていき、各ノードの数字はまだ残っている入ってくるエッジの数です。DFS 法は、あるノードより後のものがすべて置かれたら、そのノードを先頭に置きます。グラフの下の列がその時点の順序です。「閉路を追加」にチェックを入れると、各方法が閉路を見つける様子が見られます。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. カーンのアルゴリズムか DFS 法を選びます。
  2. 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。
  3. グラフの下で順序が伸びていく様子に注目しましょう。「閉路を追加」にチェックを入れると、各方法が閉路を見つける様子が見られます。

カーンのアルゴリズム

各ノードについて、そこを指すエッジが何本あるかを数えます。1本もないノードは何にも依存していないので、最初に置けます。そのようなノードを置き、そこから出るエッジを取り除きます。指されていたノードは入ってくるエッジが1本減り、0 になって置けるようになるものもあります。置けるノードがなくなるまで置き続けます。最後まで置けるようにならないノードがあれば、それらは閉路の中で互いに待ち合っていて、トポロジカル順序はありません。

DFS 法

まだ訪問していない各ノードから深さ優先探索を行います。あるノードから到達できるものがすべて終わったとき、そのノードは終わります。つまり、その後に来るべきものはすべてもう置かれています。終わったノードを順序の先頭に置いていけば、正しい順序ができます。探索が、まだその中にいるノードへのエッジをたどったら、そのエッジが閉路を閉じ、やはり順序はありません。

よくある質問

トポロジカルソートとは?

有向グラフのノードを、どのエッジも前のノードから後ろのノードへ向かうように並べた順序です。エッジが「先にやる必要がある」を表すなら、すべての作業をこなせる順番になります。

トポロジカル順序はいつ存在する?

グラフに有向閉路がないとき、そしてそのときに限ります。つまり有向非巡回グラフ(DAG)のときです。閉路があると、その上のどのノードも自分より先に来なければならなくなります。

トポロジカル順序は1つだけ?

ふつうは違います。2つのノードがエッジの連なりでつながっていなければ、どちらが先でもかまわないので、1つのグラフに正しい順序がたくさんあることがあります。カーンのアルゴリズムと DFS 法は、違う順序を出すことがよくあります。

トポロジカルソートはどれくらい速い?

どちらの方法も、すべてのノードとすべてのエッジを決まった回数だけ見るので、計算量はノード数とエッジ数の和に比例して増えます。

グラフはどこかに送信されますか?

いいえ。グラフの作成と並べ替えはブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ