🎯 この記事でわかること
- 有向グラフとは何か
- トポロジカルソートとは何か
- 「出口のない頂点」の意味
- プログラムの動き
- 基本情報技術者試験での解き方
ハク
トポロジカルソートって名前だけで難しそう…💦
レイ
安心してください。やっていることは『出口のない頂点を見つける』だけです。
ハク
えっ、それだけなの！？
🌟 トポロジカルソートとは？
順番のルールを守って並べる方法
たとえば、
設計 → 実装 → テスト → リリースのように、前後関係があるものを正しい順番に並べることを指します。
🕸️ 有向グラフとは？
矢印の向きがあるグラフのことです。
A → B
A → C
B → D
C → D
D → E
D → F🖼️ 有向グラフの図
📝 このグラフの意味
- A は B と C より前
- B と C は D より前
- D は E と F より前
🎯 トポロジカルソートの例
このグラフでは、次のような並びが可能です。
ABCDEF
ACBDEF
ABCDFE
ACBDFEどれも正解です。
🚪 出口のない頂点とは？
自分から出ていく矢印が1本もない頂点
今回のグラフでは、
- E
- F
が出口のない頂点です。
ハク
『もう次に進む場所がない』頂点なんだね！
🔄 並べた頂点は削除する
トポロジカルソートでは、
- 出口のない頂点を探す
- 並べる
- グラフから削除する
を繰り返します。
例
A → B → C最初
出口なし → C
Cを削除
A → B出口なし → B
Bを削除
A出口なし → A
「出口のない頂点」が移る
並べた頂点は消えたと考えて、出口のない頂点が他の頂点に移っていく。
これがまさに正解！
💻 プログラムの意味
// トポロジカルソート（出口のない頂点を使う方法）
整数型: n ← グラフの頂点数
文字列型の配列: array[n]
整数型: count ← 1
Vertex型: curr
while (count ≤ n)
// 1. 出口のない頂点を探す
グラフから、
自分を始点とする辺が1本もない頂点を1つ選び、
curr に格納する
// 見つからなければ循環あり
if (curr が未定義)
エラーを出力して終了
endif
// 2. 配列の後ろに入れる
array[n - count + 1] ← curr.label
// 3. グラフから削除
グラフから curr を削除する
// 4. 次へ
count ← count + 1
endwhile
// 5. 配列を先頭から出力
for (i を 1 から n まで 1 ずつ増やす)
array[i] を出力する
endforこの問題のプログラムは、次の処理をしています。
1. 出口のない頂点を探す
2. 配列の後ろに入れる
3. グラフから削除
4. 全部なくなるまで繰り返す
5. 配列を先頭から出力なぜ配列の後ろから入れるの？
最初に見つかるのは、
最後に来る頂点
だからです。
例
A → B → C見つかる順番：
C → B → A配列の後ろから入れると：
A B Cとなります。
📝 実際の処理例
A → B
A → C
B → D
C → D
D → E
D → F1回目
出口なし → E または F
2回目
もう一方の E または F
3回目
D
4回目
B または C
5回目
もう一方の B または C
6回目
A
🎯 最終結果の例
ACBDEF📝 基本情報技術者試験でのコツ
試験では、
矢印の向きに逆らっていないか
を確認すればOK！
例
A → Bなら、
- AB → OK
- BA → NG
ハク
並べたものを消していくと、出口のない頂点が変わっていくんだね！
レイ
はい。そして最初に見つかるのは、最終的に一番後ろに来る頂点です。
まとめ
トポロジカルソートとは、
出口のない頂点を見つけて削除することを繰り返し、順番のルールを守って並べる方法
です。
覚えておきたいポイント：
- 有向グラフ = 矢印付きのグラフ
- 出口のない頂点 = 出ていく矢印がない
- 並べた頂点は削除する
- 削除すると新しい出口のない頂点が現れる
- 最初に見つかるのは最後に来る頂点
- 配列の後ろから格納する
最後に
トポロジカルソートは名前こそ難しいですが、実際には
「最後に置けるものを見つけて消していく」
だけです。
この考え方がわかれば、基本情報技術者試験の有向グラフ問題はかなり解きやすくなるよ！
コメント