okinawa

IT勉強メモ

深さ優先探索のお勉強

深さ優先探索を理解するために、写経したり実装したりしてみた。

参考サイト

DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita

うさぎでもわかる2分探索木 後編 2分探索木における4つの走査方法 | 工業大学生ももやまのうさぎ塾

深さ優先探索とは

形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。

その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。 引用元:深さ優先探索 - Wikipedia

自分なりの理解

深さ優先探索とは、行けるとこまで行って、行き止まりになったら戻り、また道を探す。

計算量

全ての頂点と辺を探索するので、大体の場合は「O(頂点数+辺数)」になる。

使い所

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を探索中のデバッグモード⇩

ノード2探索スレッド


vertexNumber=探索中のノード
destination=1 が次の行き先

ノード2は次の行き先が1しか無い。
でも1はすでに探索済みだから探索終了するのでは?と思った。

ノード0とノード1の探索スレッドが残っていた

ノード1探索スレッド⇩

ノード1からノード3へはまだ行ってないので行き先が残っている。

ノード0スレッドもあるよ⇩

ノード0の探索スレッド

再帰関数の処理の流れ

ノード2の探索スレッドが終了

ノード1の探索スレッドに戻る

ノード1の探索スレッドが終了

ノード0の散策スレッドに戻る

ということでした。

さすがEclipseデバッグモードはわかりやすい。

スタックバージョン

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用にテンプレを作った。

github.com

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)

・例題
C - Ladder Takahashi