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

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法ほうなどを使用しようする。

Exercises on Graph Traversal and Unweighted Distance

1Problem 1: Paths, distance, and connected components

Let the undirected graph $$G=(V,E)$$G=(V,E) be defined by

1. List every path of length 2 from $$a$$a to $$d$$d.
2. Find $$d(a,d)$$d(a,d) and $$d(a,f)$$d(a,f).
3. Find all connected components.

1.1Solution

The length-2 paths are $$a,b,d$$a,b,d and $$a,c,d$$a,c,d. Therefore $$d(a,d)=2$$d(a,d)=2. No path joins $$a$$a to $$f$$f, so $$d(a,f)=\mathrm{\infty }$$d(a,f)=\infty. The connected components are $$\{a,b,c,d\}$$\{a,b,c,d\} and $$\{e,f\}$$\{e,f\}.

2Problem 2: DFS and BFS order

Use the graph from Problem 1 and examine every adjacency list in alphabetical order. Start at $$a$$a and mark a vertex visited when it is added to the candidates.

1. Determine the first-visit order of recursive DFS.
2. Determine the first-visit order of BFS.
3. Find the traversal levels $$\ell$$\ell recorded by BFS and verify that they equal the distances from $$a$$a to every reachable vertex.

2.1Solution

DFS visits $$a,b,d,c$$a,b,d,c. It proceeds from $$a$$a to $$b$$b, from $$b$$b to $$d$$d, and then from $$d$$d to the unvisited vertex $$c$$c.

BFS visits $$a,b,c,d$$a,b,c,d. The recorded distances are

These levels equal the lengths of the shortest paths found in Problem 1. Vertices $$e,f$$e,f are unreachable from $$a$$a.

3Problem 3: When to mark a vertex visited

Run BFS on the triangle graph

Explain what duplication may occur if a vertex is not marked visited until it is removed from the queue. Then explain why marking it when it is added prevents the duplication.

3.1Solution

Processing $$s$$s adds $$u,v$$u,v to the queue. When $$u$$u is removed, $$v$$v may still be unvisited, so edge $$\{u,v\}$$\{u,v\} can add $$v$$v again, leaving two copies of $$v$$v in the queue.

If a vertex is marked at insertion, then $$v\in S$$v\in S immediately after its first insertion. A later examination through another edge fails the condition $$v\notin S$$v\notin S, so every vertex is added to the candidates at most once.

4Problem 4: Representation, complexity, and method selection

Answer the following questions for an undirected graph with $$\left|V\right|=n$$|V|=n and $$\left|E\right|=m$$|E|=m.

1. Give the number of edge entries stored in adjacency lists and their space complexity.
2. Give the space complexity and edge-query time of an adjacency matrix, and choose a representation for a sparse graph.
3. Explain the running time of DFS and BFS with adjacency lists.
4. State whether DFS or BFS applies to unweighted shortest distance, reachability, and shortest distance with unequal edge weights.

4.1Solution

Each undirected edge appears once in the list of each endpoint, so there are $$2m$$2m edge entries and the lists, including the vertex headers, use $$O(n+m)$$O(n+m) space. An adjacency matrix uses $$O\left(n^2\right)$$O(n^2) space but answers an edge-existence query in $$O\left(1\right)$$O(1) time. Adjacency lists are preferable for a sparse graph, where $$m$$m is much smaller than $$n^2$$n^2.

With adjacency lists, each vertex is processed at most once and each undirected edge is examined at most once from each endpoint. Thus DFS and BFS run in $$O(n+m)$$O(n+m) time. Use BFS for unweighted shortest distance. Either DFS or BFS determines reachability. Neither ordinary DFS nor ordinary BFS guarantees shortest distance when edge weights differ; for nonnegative weights, use a method such as Dijkstra's algorithm.