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 になるようなアルゴリズムを選択しないといけなさそう。
というか、削除とかしてもデータ構造内部のアドレスとか変わらないだろうな。