深さ優先探索を理解するために、写経したり実装したりしてみた。
参考サイト
DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita
うさぎでもわかる2分探索木 後編 2分探索木における4つの走査方法 | 工業大学生ももやまのうさぎ塾
深さ優先探索とは
形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。
その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。 引用元：深さ優先探索 - Wikipedia
自分なりの理解
深さ優先探索とは、行けるとこまで行って、行き止まりになったら戻り、また道を探す。
計算量
全ての頂点と辺を探索するので、大体の場合は「O(頂点数＋辺数)」になる。
使い所
１．迷路問題。
スタート地点からゴール地点まで行くルートがあるかを探索する問題など。
ただし、最短ルートの探索はできない。
最短ルート探索は幅優先探索でやる。
グラフを隣接リスト表現で作ってみる
画像の引用元：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 数値は頂点０から向かう別の頂点。頂点０→頂点５に向かう辺を表す。 graph.add(vertex0);// 頂点０と辺をグラフに格納 List<Integer> vertex1 = new ArrayList<>(); vertex1.add(3);//頂点1から頂点３に向かう辺 vertex1.add(6);//頂点1から頂点６に向かう辺 graph.add(vertex1);// 頂点１と辺をグラフに格納 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);//頂点５から向かう頂点はない 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
再帰関数の面白いところ
下図のようにノード２まで行ったら未探索のノードが繋がってなくて探索終了するのでは？
と思ったがそんなことはなかった。
デバッグモードで見るとよくわかるんだが、ノード0とノード1の探索スレッドがまだ残っている。
ノード２を探索中のデバッグモード⇩
⇧
vertexNumber=探索中のノード
destination=1 が次の行き先
ノード２は次の行き先が１しか無い。
でも１はすでに探索済みだから探索終了するのでは？と思った。
ノード0とノード１の探索スレッドが残っていた
ノード１探索スレッド⇩
ノード１からノード3へはまだ行ってないので行き先が残っている。
ノード０スレッドもあるよ⇩
再帰関数の処理の流れ
ノード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] } }
DFSテンプレート
Java
AtCoder用にテンプレを作った。
Python
標準バージョン
import sys sys.setrecursionlimit(10**6)# これ入れないと再帰回数オーバーでREになる # 標準入力受け取り n, m = map(int, input().split()) g = [[] for _ in range(n)] seen = [False]*n # 標準入力を2次元配列g（グラフ）で受け取り for i in range(m): a, b = map(int, input().split())#aが頂点、bが辺を表す g[a-1].append(b-1) g[b-1].append(a-1) def dfs(num): seen[num] = True for next in g[num]: if seen[next]: continue dfs(next) dfs(0) if sum(seen) == n: print("The graph is connected.") else: print("The graph is not connected.")
計算量節約バージョン
頂点数や辺数が多くてTLEしそうなとき用
defaultdictとsetを使う。
from collections import defaultdict sys.setrecursionlimit(10**6) n = int(input()) g=defaultdict(set) seen=defaultdict() for i in range(n): a,b=map(int, input().split()) g[a].add(b) g[b].add(a) seen[a]= False seen[b] = False def dfs(v): seen[v]=True for next in g[v]: if seen[next]: continue dfs(next)
