パスワードを忘れた? アカウント作成
737749 journal

noboruの日記: トポロジカルソート

日記 by noboru

トポロジカルソートを BGL を使って実装する宿題。普通に深さ優先探索をするのではなくて、次のようにする。
 a. 入ってくる辺を 1 つも持たない頂点 (indegree 0 の頂点) を探す。
 b. その頂点を出力する。
 c. その頂点と、その頂点から出るすべての辺を削除する。
 d. 以上を繰り返す。
ただし、a. は実際には探していけなくて constant time (一定時間、つまり頂点数に依存しない時間) で得ることが条件。全体としてオーダー O(頂点の数 + 辺の数) におさえないといけない。次のような感じだろうか。
 T1. indegree 0 の頂点をすべて記憶しておくキューを作成する。実際には頂点への参照を入れる。
 T2. 最初にすべての頂点を調べてキューに入れる (O(V))。
 T3a. キューから 1 つ indegree 0 の頂点を取り出す。
 T3b. その頂点を出力する。
 T3c. その頂点と、その頂点から出るすべての辺を削除する。ただし、辺を削除する際に辺が指す先の頂点を参照し、indegree 1 だったらキューに入れる。なぜなら、いま辺を削除したら indegree 0 になるから。
 T3d. 以上を繰り返す。
こうすると、頂点を削除する処理 remove_vertex と辺を削除する処理 remove_edge が時間に影響してきそうなので、それらが constant time になるようなアルゴリズムを選択しないといけなさそう。
というか、削除とかしてもデータ構造内部のアドレスとか変わらないだろうな。

typodupeerror

目玉の数さえ十分あれば、どんなバグも深刻ではない -- Eric Raymond

読み込み中...