- 現在
- 置ける・訪問中
- 配置済み
- 閉路
トポロジカルソート
靴下の次に靴、基礎の次に壁、ある授業の次にそれを前提とする授業。トポロジカルソートは、一方向のエッジを持つグラフのノードを、どのエッジも前から後ろへ向かう1列に並べます。カーンのアルゴリズムか DFS 法を選んでステップごとに進め、順序が伸びていく様子を見てみましょう。閉路を加えると、なぜそのとき順序がありえないのかもわかります。 「再生」で順序が伸びていく様子を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。エッジはすべて矢印のとおり一方向で、「これはあれより先」という意味だと考えてください。方法を選びます。カーンのアルゴリズムは入ってくるエッジのないノードから置いていき、各ノードの数字はまだ残っている入ってくるエッジの数です。DFS 法は、あるノードより後のものがすべて置かれたら、そのノードを先頭に置きます。グラフの下の列がその時点の順序です。「閉路を追加」にチェックを入れると、各方法が閉路を見つける様子が見られます。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- カーンのアルゴリズムか DFS 法を選びます。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。
- グラフの下で順序が伸びていく様子に注目しましょう。「閉路を追加」にチェックを入れると、各方法が閉路を見つける様子が見られます。
カーンのアルゴリズム
各ノードについて、そこを指すエッジが何本あるかを数えます。1本もないノードは何にも依存していないので、最初に置けます。そのようなノードを置き、そこから出るエッジを取り除きます。指されていたノードは入ってくるエッジが1本減り、0 になって置けるようになるものもあります。置けるノードがなくなるまで置き続けます。最後まで置けるようにならないノードがあれば、それらは閉路の中で互いに待ち合っていて、トポロジカル順序はありません。
DFS 法
まだ訪問していない各ノードから深さ優先探索を行います。あるノードから到達できるものがすべて終わったとき、そのノードは終わります。つまり、その後に来るべきものはすべてもう置かれています。終わったノードを順序の先頭に置いていけば、正しい順序ができます。探索が、まだその中にいるノードへのエッジをたどったら、そのエッジが閉路を閉じ、やはり順序はありません。
よくある質問
トポロジカルソートとは?
有向グラフのノードを、どのエッジも前のノードから後ろのノードへ向かうように並べた順序です。エッジが「先にやる必要がある」を表すなら、すべての作業をこなせる順番になります。
トポロジカル順序はいつ存在する?
グラフに有向閉路がないとき、そしてそのときに限ります。つまり有向非巡回グラフ(DAG)のときです。閉路があると、その上のどのノードも自分より先に来なければならなくなります。
トポロジカル順序は1つだけ?
ふつうは違います。2つのノードがエッジの連なりでつながっていなければ、どちらが先でもかまわないので、1つのグラフに正しい順序がたくさんあることがあります。カーンのアルゴリズムと DFS 法は、違う順序を出すことがよくあります。
トポロジカルソートはどれくらい速い?
どちらの方法も、すべてのノードとすべてのエッジを決まった回数だけ見るので、計算量はノード数とエッジ数の和に比例して増えます。
グラフはどこかに送信されますか?
いいえ。グラフの作成と並べ替えはブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ