グラフ探索たんさくと無重むおもみ距離きょりの演習えんしゅう

1問題もんだい1：道みち・距離きょり・連結成分れんけつせいぶん

無向むこうグラフ $$G=(V,E)$$G=(V,E) を

で定さだめる。

1. $$a$$a から $$d$$d への長ながさ2の道みちをすべて挙あげよ。
2. $$d(a,d)$$d(a,d) と $$d(a,f)$$d(a,f) を求もとめよ。
3. 連結成分れんけつせいぶんをすべて求もとめよ。

1.1解答かいとう

長ながさ2の道みちは $$a,b,d$$a,b,d と $$a,c,d$$a,c,d である。したがって $$d(a,d)=2$$d(a,d)=2 である。$$a$$a と $$f$$f の間あいだに道みちは存在そんざいしないので $$d(a,f)=\mathrm{\infty }$$d(a,f)=\infty である。連結成分れんけつせいぶんは $$\{a,b,c,d\}$$\{a,b,c,d\} と $$\{e,f\}$$\{e,f\} である。

2問題もんだい2：DFSとBFSの順序じゅんじょ

問題もんだい1のグラフで、各隣接かくりんせつリストはアルファベット順じゅんに調しらべるものとする。始点してんを $$a$$a とし、頂点ちょうてんを候補こうほへ追加ついかした時点じてんで訪問済ほうもんずみにする。

1. 再帰的さいきてきDFSで初はじめて訪問ほうもんする頂点ちょうてんの順序じゅんじょを求もとめよ。
2. BFSで初はじめて訪問ほうもんする頂点ちょうてんの順序じゅんじょを求もとめよ。
3. BFSが記録きろくする探索たんさくレベル $$\ell$$\ell を求もとめ、$$a$$a から各到達可能頂点かくとうたつかのうちょうてんへの距離きょりと一致いっちすることを確認かくにんせよ。

2.1解答かいとう

DFSは $$a,b,d,c$$a,b,d,c の順じゅんに訪問ほうもんする。$$a$$a から $$b$$b、$$b$$b から $$d$$d へ進すすみ、$$d$$d から未訪問みほうもんの $$c$$c へ進すすむためである。

BFSは $$a,b,c,d$$a,b,c,d の順じゅんに訪問ほうもんする。距離きょりは

であり、問題もんだい1で求もとめた最短さいたんの道みちの長ながさと一致いっちする。$$e,f$$e,f は $$a$$a から到達不能とうたつふのうである。

3問題もんだい3：訪問済ほうもんずみ記録きろくの時点じてん

三角形さんかくけいグラフ

でBFSを行おこなう。頂点ちょうてんをキューから取とり出だすまで訪問済ほうもんずみにしない実装じっそうでは、どの重複ちょうふくが発生はっせいし得うるか説明せつめいせよ。また、追加時ついかじに訪問済ほうもんずみにする修正しゅうせいが重複ちょうふくを防ふせぐ理由りゆうを述のべよ。

3.1解答かいとう

$$s$$s の処理しょりで $$u,v$$u,v がキューへ入はいる。$$u$$u を取とり出だした時点じてんで $$v$$v がまだ未訪問みほうもんなら、辺へん $$\{u,v\}$$\{u,v\} により $$v$$v が再ふたたび追加ついかされ、キューに $$v$$v が二ふたつ存在そんざいし得うる。

追加ついかと同時どうじに訪問済ほうもんずみにすれば、最初さいしょに $$v$$v を追加ついかした時点じてんで $$v\in S$$v\in S となる。その後ごに別べつの辺へんから $$v$$v を調しらべても追加条件ついかじょうけん $$v\notin S$$v\notin S を満みたさないため、各頂点かくちょうてんは高々たかだか一度いちどしか候補こうほへ追加ついかされない。

4問題もんだい4：表現ひょうげん・計算量けいさんりょう・手法しゅほうの選択せんたく

$$\left|V\right|=n,\left|E\right|=m$$|V|=n, |E|=m の無向むこうグラフについて答こたえよ。

1. 隣接りんせつリストに格納かくのうされる辺へんの項目数こうもくすうと空間計算量くうかんけいさんりょうを示しめせ。
2. 隣接行列りんせつぎょうれつの空間計算量くうかんけいさんりょうと辺へんの存在判定そんざいはんていの時間計算量じかんけいさんりょうを示しめし、疎そグラフに適てきした表現ひょうげんを選えらべ。
3. 隣接りんせつリストを用もちいるDFSとBFSの時間計算量じかんけいさんりょうを説明せつめいせよ。
4. 無重むおもみ最短距離さいたんきょり、到達可能性とうたつかのうせい、辺へんの重おもみが異ことなる最短距離さいたんきょりに、それぞれDFSまたはBFSを適用てきようできるか述のべよ。

4.1解答かいとう

無向辺むこうへんは両端点りょうたんてんのリストに一度いちどずつ現あらわれるため、辺へんの項目数こうもくすうは $$2m$$2m、頂点ちょうてんのリストも含ふくめた空間計算量くうかんけいさんりょうは $$O(n+m)$$O(n+m) である。隣接行列りんせつぎょうれつは $$O\left(n^2\right)$$O(n^2) 空間くうかんを使用しようするが、辺へんの存在そんざいを $$O\left(1\right)$$O(1) 時間じかんで判定はんていできる。$$m$$m が $$n^2$$n^2 より十分小じゅうぶんちいさい疎そグラフには隣接りんせつリストが適てきしている。

隣接りんせつリストでは、各頂点かくちょうてんを高々たかだか一度いちど、各無向辺かくむこうへんを両端りょうたんから高々たかだか一度いちどずつ調しらべるため、DFSとBFSは $$O(n+m)$$O(n+m) 時間じかんで動作どうさする。無重むおもみ最短距離さいたんきょりにはBFSを使用しようする。到達可能性とうたつかのうせいにはDFSとBFSのどちらも使用しようできる。辺へんの重おもみが異ことなる場合ばあい、通常つうじょうのDFSとBFSはいずれも最短距離さいたんきょりを保証ほしょうしない。重おもみが非負ひふならDijkstra法ほうなどを使用しようする。