數據結構與算法——廣度和深度優先搜索

shmily 發布于2019-08-16 16:13 / 2481人閱讀

摘要：今天就來看看基于圖的兩種搜索算法，分別是廣度優先搜索和深度優先搜索算法，這兩個算法都十分的常見，在平常的面試當中也可能遇到。

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 + " ");
    }
}

程序中有三個輔助的變量：

一是 boolean[] visited ，這個數組表示如果已經被訪問，則設置為 true，例如頂點 s，是最開始被訪問的，直接設置為 true。

二是有一個隊列 queue，它表示的是，一個頂點已經被訪問，但是其相鄰的頂點還沒有被訪問的頂點。例如頂點 s，它自己被訪問了，但是和它相鄰的兩個頂點還沒有被訪問，因此直接被添加到了隊列當中。

三是數組 path，它表示一個頂點是被哪個頂點所訪問的，數組下標表示的是頂點，對應存儲的是由誰所訪問。這個邏輯在代碼中的體現便是 path[q] = w 這一行。最后，這個數組中存儲的便是搜索的路徑，需要遞歸打印出來。

3. 深度優先搜索

再來看看深度優先搜索，這種搜索的基本思路就是：從起始頂點出發，任意遍歷頂點，如果走不通，則回退一個頂點，然后換一個頂點繼續遍歷，知道找到目標頂點。像下圖這樣：

圖中從頂點 s 出發，藍色的表示前進的頂點，紅色的表示后退一個頂點，直到找到目標頂點 t，相信你可以看出來，這樣搜索出來的路徑其實并不是 s 到 t 的最短路徑，而是任意的一條路徑。

深度優先的代碼實現：

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 數組表示訪問的路徑。

最后，總結一下，廣度和深度優先搜索，都是比較暴力的搜索方式，沒有什么優化，層層遍歷或者一路遞歸，所以不難看出，這兩個算法的時間復雜度接近 O(n)，空間復雜度也是 O(n)，還是稍微有點高的，所以這兩種搜索算法適用于圖上的頂點數據不太多的情況。

GPU云服務器云服務器廣度優先搜索算法代碼廣度優先搜索深度優先搜索最佳優先搜索算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73974.html

學習JavaScript數據結構與算法 — 深度優先搜索算法

摘要：深度優先搜索上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。用深度優先搜索算法對圖中的任務圖進行拓撲排序最終各頂點的發現和探索完成時間會保存在中。深度優先搜索（DFS）上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。其中深度優先搜索算法會從第一個指定的頂點開始遍歷圖，沿著路徑直到這條路徑最后一個頂點，接著原路回退并探索下一條路徑。換句話說，它是先深度后廣...

李增田 2019-08-22 11:09 評論0 收藏0
算法-圖和圖算法

摘要：圖的定義用圖對現實中的系統建模可以用圖對現實中的很多系統建模比如對交通流量建模頂點可以表示街道的十字路口邊可以表示街道加權的邊可以表示限速或者車道的數量建模人員可以用這個系統來判斷最佳路線及最有可能堵車的街道任何運輸系統都可以用圖來建模比如圖的定義用圖對現實中的系統建模可以用圖對現實中的很多系統建模. 比如對交通流量建模, 頂點可以表示街道的十字路口, 邊可以表示街道. 加權的邊...

Anshiii 2019-08-23 12:15 評論0 收藏0
深度優先和廣度優先--搜索算法

摘要：樹狀結構張飛關羽劉備荀彧關平點擊曹操這一項，加載出來劉禪和周倉，點擊周倉，又異步加載項羽和別姬曹操劉禪周倉項羽別姬貂蟬深度優先對于入參的判斷，必須存在且是一個數組，如果不是，進行矯正必須是一個字符串，不能是函數之類的必須是一個函數廣度優先 1 樹狀結構 var result = { id:0, name:張飛, item:[ {id:1,name...

molyzzx 2019-08-22 18:16 評論0 收藏0
學習JavaScript數據結構與算法 — 廣度優先搜索算法

摘要：廣度優先搜索上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。其中廣度優先搜索算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪問圖的一層。其它最短路徑算法對于加權圖的最短路徑，廣度優先算法可能并不合適。廣度優先搜索（BFS）上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。其中廣度優先搜索算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的...

eternalshallow 2019-08-22 11:09 評論0 收藏0
深度優先搜索和廣度優先搜索

摘要：不撞南墻不回頭深度優先搜索基礎部分對于深度優先搜索和廣度優先搜索，我很難形象的去表達它的定義。這就是深度優先搜索了，當然，這個題目我們還有別的解法，這就到了我們說的廣度優先搜索。不撞南墻不回頭-深度優先搜索基礎部分對于深度優先搜索和廣度優先搜索，我很難形象的去表達它的定義。我們從一個例子來切入。輸入一個數字n，輸出1~n的全排列。即n=3時，輸出123，132，213，231，...

huaixiaoz 2019-07-31 10:02 評論0 收藏0