數(shù)據(jù)結(jié)構(gòu)與算法——廣度和深度優(yōu)先搜索

shmily 發(fā)布于2019-08-16 16:13 / 2490人閱讀

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

1. 概論

前面說到了圖這種非線性的數(shù)據(jù)結(jié)構(gòu)，并且我使用了代碼，簡單演示了圖是如何實現(xiàn)的。今天就來看看基于圖的兩種搜索算法，分別是廣度優(yōu)先搜索和深度優(yōu)先搜索算法，這兩個算法都十分的常見，在平常的面試當(dāng)中也可能遇到。

在圖上面的搜索算法，其實主要的表現(xiàn)形式就是從圖中的一個頂點，找到和另一個頂點之間的路徑，而兩種搜索算法，都是解決這個問題的。

2. 廣度優(yōu)先搜索

廣度優(yōu)先搜索的基本思路就是從一個頂點出發(fā)，層層遍歷，直到找到目標(biāo)頂點，其實這樣搜索出來的路徑也就是兩個頂點之間的最短距離。如下圖所示，例如要搜索出頂點 s -> t 的路徑，搜索的方式就是這樣的：

其中黃色的線條表示搜索的節(jié)點，數(shù)字 1、2、3、4 表示搜索的次序，廣度優(yōu)先搜索的原理看起來十分的簡單，但是它的代碼實現(xiàn)還是稍微有點難的，先來看看整體的代碼實現(xiàn)，然后再具體講解一下：

public class BFS {

    /**
     * 廣度優(yōu)先搜索算法
     * @param graph 圖
     * @param s 搜索的起點（對應(yīng)圖中的一個頂點）
     * @param t 搜索的終點
     */
    public static void bfs(Graph graph, int s, int t){
        if (s == t) return;

        //獲得圖的頂點個數(shù)
        int vertex = graph.getVertex();
        //獲取存儲圖頂點的列表
        LinkedList[] list = graph.getList();
        //如果某個頂點已經(jīng)被訪問，則設(shè)置為true
        boolean[] visited = new boolean[vertex];
        visited[s] = true;
        //隊列，存儲的是已經(jīng)被訪問，但是其相連的頂點還沒有被訪問的頂點
        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 ，這個數(shù)組表示如果已經(jīng)被訪問，則設(shè)置為 true，例如頂點 s，是最開始被訪問的，直接設(shè)置為 true。

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

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

3. 深度優(yōu)先搜索

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

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

深度優(yōu)先的代碼實現(xiàn)：

public class DFS {

    //判斷是否找到了目標(biāo)頂點
    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 和廣度優(yōu)先搜索一樣，都是表示訪問過的節(jié)點設(shè)置為 true，path 數(shù)組表示訪問的路徑。

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

云服務(wù)器 GPU云服務(wù)器廣度優(yōu)先搜索算法代碼廣度優(yōu)先搜索深度優(yōu)先搜索最佳優(yōu)先搜索算法

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/73974.html

發(fā)表評論

登陸后可評論

0條評論

shmily

男|高級講師

我要關(guān)注我要私信

TA的文章

dns主機別名怎么用-私人dns主機名設(shè)置？

閱讀 4604·2021-09-22 14:57
使用es6實現(xiàn)iview的選項卡切換

閱讀 565·2019-08-30 15:56
掌握緩存，不再讓你藍(lán)瘦香菇

閱讀 2672·2019-08-30 15:53
Skeleton Screen -- 骨架屏

閱讀 2245·2019-08-29 14:15
字符串截取的幾種辦法（php，js，css三種）

閱讀 1692·2019-08-28 17:54
網(wǎng)頁加密16進(jìn)制

閱讀 564·2019-08-26 13:37
Cookie就擺在那，為什么死活吃不到？

閱讀 3484·2019-08-26 10:57
熱播劇因“問題地圖”踩雷，創(chuàng)作平臺如何規(guī)避？

閱讀 1049·2019-08-26 10:32

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

數(shù)據(jù)結(jié)構(gòu)與算法——廣度和深度優(yōu)先搜索

相關(guān)文章

**學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — 深度優(yōu)先搜索算法**

算法-圖和圖算法

**深度優(yōu)先和廣度優(yōu)先--搜索算法**

**學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — 廣度優(yōu)先搜索算法**

**深度優(yōu)先搜索和廣度優(yōu)先搜索**

發(fā)表評論

0條評論

shmily

男|高級講師

TA的文章

dns主機別名怎么用-私人dns主機名設(shè)置？

使用es6實現(xiàn)iview的選項卡切換

掌握緩存，不再讓你藍(lán)瘦香菇

Skeleton Screen -- 骨架屏

字符串截取的幾種辦法（php，js，css三種）

網(wǎng)頁加密16進(jìn)制

Cookie就擺在那，為什么死活吃不到？

熱播劇因“問題地圖”踩雷，創(chuàng)作平臺如何規(guī)避？

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

數(shù)據(jù)結(jié)構(gòu)與算法——廣度和深度優(yōu)先搜索

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！