深さ優先探索を理解するために、写経したり実装したりしてみた。
参考サイト
DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita
うさぎでもわかる2分探索木 後編 2分探索木における4つの走査方法 | 工業大学生ももやまのうさぎ塾
深さ優先探索とは
形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。
その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。 引用元:深さ優先探索 - Wikipedia
使い所
1.迷路問題。
スタート地点からゴール地点まで行くルートがあるかを探索する問題など。
ただし、最短ルートの探索はできない。
最短ルート探索は幅優先探索でやる。
グラフを隣接リスト表現で作ってみる
画像の引用元:DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita
上図の有向グラフを作ってみた。
package atcoder; import java.util.ArrayList; import java.util.List; public class DirectdGraph { //有向グラフを写経。隣接リスト表現 public static void main(String[] args) { // グラフ List<List<Integer>> graph = new ArrayList<>(); // 頂点 List<Integer> vertex0 = new ArrayList<>(); vertex0.add(5);//頂点0 数値は頂点0から向かう別の頂点。頂点0→頂点5に向かう辺を表す。 graph.add(vertex0);// 頂点0と辺をグラフに格納 List<Integer> vertex1 = new ArrayList<>(); vertex1.add(3);//頂点1から頂点3に向かう辺 vertex1.add(6);//頂点1から頂点6に向かう辺 graph.add(vertex1);// 頂点1と辺をグラフに格納 List<Integer> vertex2 = new ArrayList<>(); vertex2.add(5);//頂点2 vertex2.add(7);//頂点2 graph.add(vertex2); List<Integer> vertex3 = new ArrayList<>(); vertex3.add(0);//頂点3 vertex3.add(7);//頂点3 graph.add(vertex3); List<Integer> vertex4 = new ArrayList<>(); vertex4.add(1);//頂点4 vertex4.add(2);//頂点4 vertex4.add(6);//頂点4 graph.add(vertex4); List<Integer> vertex5 = new ArrayList<>(); graph.add(vertex5);//頂点5から向かう頂点はない List<Integer> vertex6 = new ArrayList<>(); vertex6.add(7);//頂点6 graph.add(vertex6); List<Integer> vertex7 = new ArrayList<>(); vertex7.add(0);//頂点7 graph.add(vertex7); System.out.println(graph);//[[5], [3, 6], [5, 7], [0, 7], [1, 2, 6], [], [7], [0]] } }
木構造を深さ優先探索する
画像の引用元:DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita
再帰関数バージョン
想定通り0~14の順番で探索してくれた。
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class DepthFirstSearch { //再帰関数 private void dfs(List<List<Integer>> graph, List<Boolean> seen, int vertexNumber) { // 訪れた頂点を探索済みとする seen.set(vertexNumber, true); System.out.print(vertexNumber+ " ");//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // 深さ優先で探索する for (int i = 0; i < graph.get(vertexNumber).size(); i++) {//辺の数分繰り返す //行き先 int destination = graph.get(vertexNumber).get(i); if (seen.get(destination)) { // 探索済みならスキップ continue; } dfs(graph, seen, destination);// 再帰。次の行き先を渡す。 } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();//頂点数 // グラフ List<List<Integer>> graph = new ArrayList<>(); // 探索済み判定用 List<Boolean> seen = new ArrayList<>(); //グラフを入力から受け取る for (int i = 0; i < n; i++) {//頂点数分繰り返す int m = sc.nextInt();//辺の数 // 頂点 List<Integer> vertex = new ArrayList<>(); for (int j = 0; j < m; j++) {//辺の数分繰り返す vertex.add(sc.nextInt());//繋がっているノードを受け取る } // 頂点の数だけ探索判定用リストも作る seen.add(false); //頂点と辺をグラフに格納 graph.add(vertex); } DepthFirstSearch d = new DepthFirstSearch(); d.dfs(graph, seen, 0); System.out.println(seen);//[true, true, true, true, true, true, true, true] } }
入力値
N=ノードの数
Mi=繋がるノードの数(辺の数)
Ai = 繋がっているノード
入力例:
2 ←ノードの数 3 ←繋がるノードの数 繋がっているノード→1 4 11 3 0 2 3
画像の木構造に対応した入力値⇩
15 3 1 4 11 3 0 2 3 1 1 1 1 3 0 5 8 3 4 6 7 1 5 1 5 3 4 9 10 1 8 1 8 3 0 12 13 1 11 2 11 14 1 13
再帰関数の面白いところ
下図のようにノード2まで行ったら未探索のノードが繋がってなくて探索終了するのでは?
と思ったがそんなことはなかった。
デバッグモードで見るとよくわかるんだが、ノード0とノード1の探索スレッドがまだ残っている。
ノード2を探索中のデバッグモード⇩
⇧
vertexNumber=探索中のノード
destination=1 が次の行き先
ノード2は次の行き先が1しか無い。
でも1はすでに探索済みだから探索終了するのでは?と思った。
ノード0とノード1の探索スレッドが残っていた
ノード1探索スレッド⇩
ノード1からノード3へはまだ行ってないので行き先が残っている。
ノード0スレッドもあるよ⇩
再帰関数の処理の流れ
ノード2の探索スレッドが終了
⇩
ノード1の探索スレッドに戻る
⇩
ノード1の探索スレッドが終了
⇩
ノード0の散策スレッドに戻る
ということでした。
スタックバージョン
0 11 13 14 12 4 8 10 9 5 7 6 1 3 2 と再帰関数バージョンとは逆回りの深さ優先探索になった。
package atcoder; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.List; import java.util.Scanner; // 深さ優先探索(スタックバージョン) public class DepthFirstSearch3 { // Double Ended Queue(両端キュー)先入れ先出しと後入れ先出しのどちらにも対応 private static Deque<Integer> deque = new ArrayDeque<>(); private static List<List<Integer>> graph; private static List<Boolean> seen; private void dfs() { // スタックが空になるまで while (deque.isEmpty() == false) { //スタックからノードを取り出す。取り出すとスタックから削除される int vertexNumber = deque.pop(); System.out.print(vertexNumber+ " ");//0 11 13 14 12 4 8 10 9 5 7 6 1 3 2 // 訪れたノードを探索済みとする seen.set(vertexNumber, true); // 深さ優先で探索する for (int i = 0; i < graph.get(vertexNumber).size(); i++) {//繋がるノードの数分繰り返す //行き先 int destination = graph.get(vertexNumber).get(i); if (seen.get(destination) == false) { // 未探索ノードをスタック deque.push(destination); } } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();//ノード数 // グラフ graph = new ArrayList<>(); // 探索済み判定用 seen = new ArrayList<>(); //グラフを入力から受け取る for (int i = 0; i < n; i++) {//ノード数分繰り返す int m = sc.nextInt();//繋がるノードの数 // ノード List<Integer> vertex = new ArrayList<>(); for (int j = 0; j < m; j++) {//繋がるノードの数分繰り返す vertex.add(sc.nextInt());//繋がっているノードを受け取る } // ノードの数だけ探索判定用リストも作る seen.add(false); //ノード&繋がるノードをグラフに格納 graph.add(vertex); } DepthFirstSearch3 d = new DepthFirstSearch3(); // スタート地点をスタック deque.push(0); d.dfs(); System.out.println(seen);//[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true] } }