基本情報の勉強をしていますが、有向グラフとトポロジカルソートの処理が全くわかりませんでした。
そのため、GPTさんに説明してもらいました。
いきなり結論
自分に向かう矢印が0の文字から処理をして、配列に代入したらその文字を消します。
すると、また0になる文字ができるのでそれをマタ代入することを続けます。
いまいちわかっていませんが、
今回は
CABDEF
となりましたが
ACBDEF
ともなるようです。
～～～追記～～～
もっとありました
以下は可能なトポロジカルソートの結果です：
Aから始める場合:
A, C, B, D, F, E
A, C, B, F, D, E
A, C, B, F, E, D
など
Cから始める場合:
C, A, B, D, F, E
C, A, B, F, D, E
C, A, B, F, E, D
など
～～～～～～～～
有向グラフ:下記の関係性を持つグラフとする。
A -> B -> F -> E
|
v
D -> E
^
|
C
処理順
入次数の初期状態
A: 0
B: 1 (Aから)
C: 0
D: 2 (BとCから)
F: 1 (Bから)
E: 2 (DとFから)
初期キューの作成:
入次数が0のノードをキューに入れます。この場合、ノードAとノードCが入次数0です。
キュー: [C, A]
トポロジカルソートの実行:
- キューからノードCを取り出し、結果のリストに追加します。
ソート結果: [C]
キュー: [A]
ノードCから出ている辺を探し、その辺の目的地の入次数を1減らします。ノードCからはノードDへの辺がありますので、ノードDの入次数を1減らします。
Dの入次数: 1 (2から1に減少)
- キューからノードAを取り出し、ソート結果のリストに追加します。
ソート結果: [C, A]
キュー: []
ノードAから出ている辺を探し、その辺の目的地の入次数を1減らします。ノードAからはノードBへの辺がありますので、ノードBの入次数を1減らします。
Bの入次数: 0 (1から0に減少)
入次数が0になったノードBをキューに追加します。
キュー: [B]
- キューからノードBを取り出し、ソート結果のリストに追加します。
ソート結果: [C, A, B]
キュー: []
ノードBから出ている辺を探し、その辺の目的地の入次数を1減らします。ノードBからはノードDとノードFへの辺がありますので、これらのノードの入次数をそれぞれ1減らします。
Dの入次数: 0 (1から0に減少)
Fの入次数: 0 (1から0に減少)
入次数が0になったノードDとノードFをキューに追加します。
キュー: [D, F]
- キューからノードDを取り出し、ソート結果のリストに追加します。
ソート結果: [C, A, B, D]
キュー: [F]
ノードDから出ている辺を探し、その辺の目的地の入次数を1減らします。ノードDからはノードEへの辺がありますので、ノードEの入次数を1減らします。
Eの入次数: 1 (2から1に減少)
- キューからノードFを取り出し、ソート結果のリストに追加します。
ソート結果: [C, A, B, D, F]
キュー: []
ノードFから出ている辺を探し、その辺の目的地の入次数を1減らします。ノードFからはノードEへの辺がありますので、ノードEの入次数を1減らします。
Eの入次数: 0 (1から0に減少)
入次数が0になったノードEをキューに追加します。
lessCopy code
キュー: [E]
- キューからノードEを取り出し、ソート結果のリストに追加します。
ソート結果: [C, A, B, D, F, E]
キュー: []
ノードEから出ている辺はありませんので、入次数の処理は行いません。キューは空になり、ソートされていないノードもなくなりましたので、トポロジカルソートは完了です。
最終結果:
[C, A, B, D, F, E]
この手順を通じて、与えられた有向グラフに対してトポロジカルソートを行い、結果として**CABDEF**の順序を得ることができました。
くそめんどい。