深さ優先探索のお勉強

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

参考サイト
深さ優先探索とは
使い所
グラフを隣接リスト表現で作ってみる
木構造を深さ優先探索する
- 再帰関数バージョン
- スタックバージョン

参考サイト

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

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

深さ優先探索とは

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

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

使い所

１．迷路問題。

スタート地点からゴール地点まで行くルートがあるかを探索する問題など。

ただし、最短ルートの探索はできない。

最短ルート探索は幅優先探索でやる。

グラフを隣接リスト表現で作ってみる

画像の引用元：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

画像の木構造に対応した入力値⇩

再帰関数の面白いところ

下図のようにノード２まで行ったら未探索のノードが繋がってなくて探索終了するのでは？

と思ったがそんなことはなかった。

デバッグモードで見るとよくわかるんだが、ノード0とノード1の探索スレッドがまだ残っている。

ノード２を探索中のデバッグモード⇩

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

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

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

ノード１探索スレッド⇩

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

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

再帰関数の処理の流れ

ノード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]
    }

}

okinawa

IT勉強メモ