データ構造とアルゴリズム-広さと深さの優先検索

1.概説
図のような非線形なデータ構造について述べ,コードを用いて図がどのように実現されるかを簡単に実証した.今日は図に基づく2つの検索アルゴリズムを見てみましょう.それぞれ広さ優先検索と深さ優先検索アルゴリズムです.この2つのアルゴリズムはよく見られますが、普段の面接でも遭遇する可能性があります.
図の上の検索アルゴリズムでは、主な表現形式は図の中の1つの頂点から、別の頂点との間の経路を見つけることであり、2つの検索アルゴリズムは、この問題を解決している.
2.広さ優先検索
広さ優先探索の基本構想は,1つの頂点から出発し,ターゲット頂点が見つかるまで,実際には2つの頂点間の最短距離を探索することである.次の図に示すように、頂点s->tのパスを検索するには、次のようにします.
このうち黄色の線は探索のノードを表し、数字1、2、3、4は探索の順序を表し、広さ優先探索の原理は非常に簡単に見えるが、そのコード実現はまだ少し難しい.まず全体のコード実現を見てから、具体的に説明する.

public class BFS {

    /**
     *         
     * @param graph  
     * @param s      （         ）
     * @param t      
     */
    public static void bfs(Graph graph, int s, int t){
        if (s == t) return;

        //        
        int vertex = graph.getVertex();
        //          
        LinkedList[] list = graph.getList();
        //           ，    true
        boolean[] visited = new boolean[vertex];
        visited[s] = true;
        //  ，         ，                 
        Queue queue = new LinkedList<>();
        queue.add(s);
        //       
        int[] path = new int[vertex];
        for (int i = 0; i < vertex; i++) {
            path[i] = -1;
        }

        while (queue.size() != 0){
            int w = queue.poll();
            for (int i = 0; i < list[w].size(); i++) {
                int q = list[w].get(i);
                if (!visited[q]){
                    path[q] = w;
                    if (q == t){
                        print(path, s, t);
                        return;
                    }
                    visited[q] = true;
                    queue.add(q);
                }
            }
        }
    }

    //     s-t    
    private static void print(int[] prev, int s, int t){
        if (prev[t] != -1 && t != s){
            print(prev, s, prev[t]);
        }
        System.out.print(t + " ");
    }
}

プログラムには3つの補助変数があります.
1つはboolean[]visitedで、この配列はすでにアクセスされている場合、頂点sなどのtrueに設定され、最初にアクセスされ、直接trueに設定されていることを示しています.
2つ目は、1つの頂点がアクセスされているが、隣接する頂点がまだアクセスされていない頂点を表すキューqueueです.例えば、頂点sは、自身がアクセスされているが、隣接する2つの頂点はまだアクセスされていないため、キューに直接追加される.
3つ目は、1つの頂点がどの頂点によってアクセスされているかを表し、配列の下には頂点が表示され、対応する記憶されているのは誰がアクセスしているかを表します.この論理がコードに現れるのはpath[q]=wという行である.最後に,この配列に格納されているのは探索の経路であり,再帰的に印刷する必要がある.
3.深さ優先検索
深さ優先検索を見てみましょう.この検索の基本的な考え方は、開始頂点から頂点を任意に遍歴し、うまくいかない場合は頂点をロールバックし、頂点を交換して遍歴を続け、ターゲット頂点を見つけることを知ることです.次のようになります.
図中は頂点sから出発して、青いのは前進する頂点を表して、赤いのは1つの頂点を後退して、目標の頂点tを見つけるまで、あなたが見ることができることを信じて、このように捜索した経路は実はsからtの最短の経路ではありませんて、任意の1本の経路です.
深度優先コード実装:

public class DFS {

    //           
    private static boolean found =  false;

    public static void dfs(Graph graph, int s, int t){
        int vertex = graph.getVertex();
        boolean[] visited = new boolean[vertex];

        int[] path = new int[vertex];
        for (int i = 0; i < vertex; i++) {
            path[i] = -1;
        }

        LinkedList[] list = graph.getList();
        recursionDfs(list, s, t, visited, path);
        print(path, s, t);
    }

    //    
    private static void recursionDfs(LinkedList[] list, int w, int t, boolean[] visited, int[] path){
        if (found) return;

        visited[w] = true;
        if (w == t){
            found = true;
            return;
        }

        for (int i = 0; i < list[w].size(); i++) {
            int q = list[w].get(i);
            if (!visited[q]){
                path[q] = w;
                recursionDfs(list, q, t, visited, path);
            }
        }
    }
    private static void print(int[] path, int s, int t){
        if (path[t] != -1 && t != s){
            print(path, s, path[t]);
        }
        System.out.print(t + " ");
    }
}

変数boolean[]visitedは広さ優先検索と同様に,アクセスしたノードがtrueに設定され,path配列がアクセスの経路を表す.
最後に,広さと深さ優先探索は,いずれも比較的暴力的な探索方式であり,最適化はなく,幾重にも遍歴したり再帰したりしているので,この2つのアルゴリズムの時間的複雑度はO(n)に近く,空間的複雑度もO(n)であり,やや高いため,この2つの探索アルゴリズムは図上の頂点データがあまり多くない場合に適していることがわかる.