アルゴリズム設計・解析特論第 2 回レポート

600P031-4 高木祐介提出日 2000-05-30

6.8

図 6.38 で頂点の順序を a, b, ⋯, f として、深さ優先の極大森を作れ。木の弧、先行弧、後退弧、交差弧を区別せよ。各頂点の深さ優先探索番号を示せ。

\begin{matrix}頂点 & 隣接リスト & 深さ優先探索番号 \\ a & b, d, f & 1 \\ b & c, f & 2 \\ c & d & 3 \\ d & b & 4 \\ e & d, f & 6 \\ f & d & 5 \end{matrix}

\begin{matrix}弧 & 弧の種類 \\ a → b & 木の弧 \\ a → d & 先行弧 \\ a → f & 先行弧 \\ b → c & 木の弧 \\ b → f & 木の弧 \\ c → d & 木の弧 \\ d → b & 後退弧 \\ e → d & 交差弧 \\ e → f & 交差弧 \\ f → d & 交差弧 \end{matrix}

6.15

図 6.38 の強成分を求めよ。

頂点再帰呼出しが終わった順 G_{r} の隣接リスト
a  5
b  4  a, d
c  2  b
d  1  a, c, e, f
e  6
f  3  a, b, e

\begin{matrix}G_{r} の弧 & 弧の種類 \\ b → a & 交差弧 \\ b → d & 木の弧 \\ c → b & 後退弧 \\ d → a & 交差弧 \\ d → c & 木の弧 \\ d → e & 交差弧 \\ d → f & 木の弧 \\ f → a & 交差弧 \\ f → b & 後退弧 \\ f → e & 交差弧 \end{matrix}

したがって、図 6.38 の強成分は、

{a}, {b, c, d, f}, {e}

となります。

6.19

e 本の辺と n 個の頂点を持つ有向グラフに強連結のアルゴリズムを適用すると、 n ≤ e のとき O(e) 時間かかることを示せ。

強連結のアルゴリズムは、

(1) 与えられた有向グラフ G に対して深さ優先探索を行い、再帰呼出しが終わった順で頂点に番号をつける。

(2) G のすべての弧を逆向きにした新しい有向グラフ G_{r} を作る。

(3) ステップ 1 で最も大きな番号をつけた頂点を出発点として、 G_{r} に対して深さ優先探索を行う。弧の探索で到達できない頂点があったら、その中で最大の番号をつけられた頂点を出発点として、再度深さ優先探索を行う。

(4) こうして得られた極大森を構成する木 1 つ 1 つが G の強連結成分である。というものです。まず、ステップ 1 ですが、 n ≤ e の有向グラフに対して深さ優先探索を行

うと、 O(e) 時間かかります。 1 つの頂点に関して 0 回または 1 回 dfs を呼び、 dfs(v) は O(|L[v]|) なので、全体で ∑_{i=1}^{n} O(|L[v_{i}]|) = O(e) だからです。再帰呼出しが終わった順で頂点に番号をつけるのは、 1 つの頂点に関して O(1)、全体で O(n) です。 n ≤ e なので、全体として O(e + n) = O(e) 時間かかります。

ステップ 2 も O(e) です。 G の弧 v → w に対して、 G_{r} は弧 w → v を持ち、全体で e 本の弧を持っています。 G の弧を 1 本づつ見ていき、 G_{r} の弧を作るのに、 O(e) 時間かかります。

ステップ 3 は、ステップ 1 と同じ深さ優先探索なので、 O(e) 時間かかります。

4 は、すでに解が得られているので、ステップではありません。これらの結果を総合すると、 O(e) + O(e) + O(e) = O(e) で、全体として

O(e) 時間かかります。

O(e) の条件

強連結のアルゴリズムが O(e) 時間で終わるためには、いくつかの条件があります。

n ≤ e が成り立っていなければ、ステップ 1 は O(n) 時間かかります。多くの頂点を持ち、弧がほとんどない有向グラフに対して、強連結のアルゴリズムは O(n) 時間かかってしまいます。

ステップ 2 では、 G を見て G_{r} の弧を作るのに O(e) 時間かかります。ただし、これは、 G の弧 v → w を見て G_{r} の弧 w → v を作るのに O(1) 時間しかかからないと仮定した場合です。

G が隣接行列で表現されていれば、転置行列を求めることになります。 n×n の転置行列を求めるには O(n^{2}) 時間かかります。この場合、 n^{2} ≤ e でなければ、アルゴリズム全体に O(n^{2}) 時間かかってしまいます。

G が隣接リストで表現されていれば、弧を 1 本づつ見ていき、 G_{r} の隣接リストを作ることになります。隣接リストの大きさは O(e) ですが、 G_{r} の弧 1 本につき、それぞれ O(1) 時間でリストに追加しなければなりません。リストの頭に追加したり、追加位置のポインタを保持したりすれば良いのですが、 1 本追加するごとにリストの頭から尾までポインタをたどるような馬鹿な実現法を採ると、最悪 O(n × e) 時間かかってしまいます。