dfs、bfs 的終於弄明白了

前言

你問一個人聽過哪些算法，那麼深度優先搜索 (dfs) 和寬度優先搜索 (bfs) 那肯定在其中，很多小老弟學會 dfs 和 bfs 就覺得好像懂算法了，無所不能，確實如此，學會 dfs 和 bfs 暴力搜索枚舉確實利用計算機超強計算大部分都能求的一份解，學會 dfs 和 bfs 去暴力杯混分是一個非常不錯的選擇！

五大經典算法的回溯算法其實也是 dfs 的一種應用，是不是回憶起被折磨的八皇后問題。基礎的 dfs 和 bfs 學習來思想很容易，寫出來模板代碼也不難，但很多時候需要在此基礎上靈活變通就有不小難度了。

不過 dfs 和 bfs 初步學習搞懂原理比較簡單，但是想要精通 dfs 和 bfs 還是很難的，因爲很多問題是在此基礎上進行變形優化的，比如 dfs 你可能考慮各種剪枝問題，bfs 可能會涉及很多貪心的策略，有的還要考慮到記憶化的問題、雙向 bfs、bfs+dfs 等等才能更好解決的問題，不過本文講的相對基礎，不同的延伸需要自己刷題去學習纔行。

鄰接矩陣和鄰接表

dfs 和 bfs 一般用於處理圖論的問題，那麼在看問題之前首先要關注圖的存儲問題，正常一般用鄰接矩陣或者鄰接表存儲圖 (對於十字鏈表、壓縮矩陣之類空間優化這裏不進行討論)。

鄰接矩陣：
鄰接矩陣就是用數組 (二維) 表示圖，通常這種圖我們會對各個節點順序的編號，在矩陣內數值表示圖的聯通情況或者路徑長度。

如果是無權圖：那麼一般用 boolean 數組的 01 表示聯通性，如果是有權圖那麼數組的值就用來表示兩者路徑長度，如果爲 0 那麼就表示不通。另外如果圖是無向圖那麼這個矩陣是對稱的，如果是有向圖那麼大概率不是對稱的。

具體可以看下面例子，這種操作方式條理更清晰並且操作方便，當然，這種情況很容易造成空間浪費，所以有人進行空間優化，或者是鄰接表的方式存儲圖。

鄰接表：

觀察上面的鄰接矩陣，如果節點很多但是聯通路徑很少，那麼就浪費了太多的存儲空間，這種情況就更適合鄰接表。

鄰接表一般是數組套鏈表，比起鄰接矩陣節省不少空間 (直接存儲聯通信息或者路徑)，在存儲的時候可以根據數據格式要求靈活運用容器 (無權圖省事一些)。

但是正常的無向圖依然會重複浪費一半空間，就有十字鏈表，多重鏈接表等等出現優化 (大佬們的優化是真的牛批)，但在算法邏輯上稍複雜，不過一般圖論算法更注重的是算法的優化這裏就不介紹十字鏈表等，一個鄰接表存儲的圖可以看下圖：

深度優先搜索 (dfs)

概念：

深度優先搜索屬於圖算法的一種，英文縮寫爲 DFS 即 Depth First Search. 其過程簡要來說是對每一個可能的分支路徑深入到不能再深入爲止，而且每個節點只能訪問一次.

簡單的說，dfs 就是在一個圖中按照一個規則進行搜索，一般基於遞歸實現，對於我們來說 dfs 就像一個黑魔法一樣，設計好算法它就自動搜索，所以我們要注意的是算法初始化、搜索規則、結束條件。二叉樹的前序遍歷就是一個最簡單的 dfs 遍歷。

我們通常使用鄰接表或者鄰接矩陣儲存圖的信息，這裏例子使用鄰接矩陣完成！

對於 dfs 的流程來說，大致可以認爲是這樣：

(1) 某個節點開始先按照一個方向一直遍歷到盡頭，同時標記已經走過的點。

(2) 遍歷到盡頭後回退到上一個點，同時清除當前點的標記。往下一個方向遍歷一次，然後繼續重複步驟 (1).

(3) 一直到所有流程都走完，即回退到起點。

在遍歷的過程中記得需要標記 因爲不進行標記會出現死循環，標記就代表這個點被用過不能用了，而撤回標記就說明這個點又能重新使用了。

舉個例子，例如一個全排列s a i 當 s 被枚舉到就要標記這個s不能被使用 (不可能 ssss 一直下去吧)，並且遍歷到s a時候a也不能使用，到s a i 時候到盡頭回退 s a 依然要回退s 此時 a和i都被解但是上次指標方向爲a(for 循環到的位置)，那麼下一次就要往下個方向i 組成s i, 然後在s i a，同理回退到s i, 到s，下面兩個方向都被枚舉過所以還要回退到，解放了s a i但是第一個方向s已經走過，開始從a 剩下的步驟依次類推就得到了。

不過全排列這是一維空間的 dfs 運用，在標記時候可以選擇 boolean 數組對應位置 true 標記用過，false 表示沒用過。除此之外也可使用動態數組 List 使用過先刪除對應位置元素向下遞歸進行搜索，然後結束後再對應位置插入也行 (不是很推薦，效率比較低)。

對於上面圖片中圖的 dfs，得到其中一個 dfs 搜索的序列 (可能有多個) 可以用代碼來表示一下：

public class dfs {
    static boolean isVisit[];
    public static void main(String[] args) {
        int map[][]=new int[7][7];
        isVisit=new boolean[7];
        map[0][1]=map[1][0]=1;
        map[0][2]=map[2][0]=1;
        map[0][3]=map[3][0]=1;

        map[1][4]=map[4][1]=1;
        map[1][5]=map[5][1]=1;
        map[2][6]=map[6][2]=1;
        map[3][6]=map[6][3]=1;

        isVisit[0]=true;
        dfs(0,map);//從0開始遍歷
    }
    private static void dfs(int index,int map[][]) {
        // TODO Auto-generated method stub
        System.out.println("訪問"+(index+1)+"  ");
        for(int i=0;i<map[index].length;i++)//查找聯通節點
        {
            if(map[index][i]>0&&isVisit[i]==false)
            {
                isVisit[i]=true;
                dfs(i,map);
            }
        }
        System.out.println((index+1)+"訪問結束 ");
    }
}

大致順序訪問爲

廣度優先搜素 (bfs)

概念：

BFS，其英文全稱是 Breadth First Search。BFS 並不使用經驗法則算法。從算法的觀點，所有因爲展開節點而得到的子節點都會被加進一個先進先出的隊列中。一般的實驗裏，其鄰居節點尚未被檢驗過的節點會被放置在一個被稱爲 open 的容器中（例如隊列或是鏈表），而被檢驗過的節點則被放置在被稱爲 closed 的容器中。（open-closed 表）

簡單來說，bfs 就是從某個節點開始按層遍歷，估計大部分人第一次接觸 bfs 的時候是在學習數據結構的二叉樹的層序遍歷！藉助一個隊列一層一層遍歷。第二次估計就是在學習圖論的時候，給你一個圖，讓你寫出一個 bfs 遍歷的順序，此後再無 bfs…

如果從路徑上走來看，dfs 就是一條跑的很快的瘋狗，到處亂咬，沒路了就跑回來去其他地方繼續，而 bfs 就像是一團毒氣，慢慢延伸！

在實現上樸素的 bfs 就是控制一個隊列，後進先出進行層序遍歷，但很多時候可能有場景需求節點有權值可能就需要使用優先隊列。

就拿上述的圖來說，我們使用鄰接表來實現一個 bfs 遍歷。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class bfs {
    public static void main(String[] args) {
        List<Integer> map[]=new ArrayList[7];
        boolean isVisit[]=new boolean[7];
        for(int i=0;i<map.length;i++)//初始化
        {
            map[i]=new ArrayList<Integer>();
        }
        map[0].add(1);map[0].add(2);map[0].add(3);
        map[1].add(0);map[1].add(4);map[1].add(5);
        map[2].add(0);map[2].add(6);
        map[3].add(0);map[3].add(6);
        map[4].add(1);
        map[5].add(1);
        map[6].add(2);map[6].add(3);

        Queue<Integer>q1=new ArrayDeque<Integer>();
        q1.add(0);isVisit[0]=true;
        while (!q1.isEmpty()) {
            int va=q1.poll();
            System.out.println("訪問"+(va+1));
            for(int i=0;i<map[va].size();i++)
            {
                int index=map[va].get(i);
                if(!isVisit[index])
                {
                    q1.add(index);
                    isVisit[index]=true;
                }
            }
        }
    }
}

搜索之延伸

本文主要任務是幫助初學者認清 dfs 和 bfs，比較偏基礎，但是事實中 dfs 和 bfs 比較偏向實戰。

對於 dfs 和 bfs，有些區別也有些共性，例如在迷宮很多問題 dfs 能解決 bfs 也能解決。

對於 dfs 一般解決的經典問題有：

而 bfs 一般解決的問題有：

當然這裏面羅列不全，dfs 關注更多的可能是剪枝問題或者記憶化，剪枝就是剪掉沒必要的搜索，記憶化就是防止太多重複操作。而 bfs 關注更多的可能是貪心策略選擇 (大部分搜索可能有一些附加的條件) 可能需要使用優先隊列來解決。

然而，當數據達到一定程度，我們使用簡單的方法肯定會爆炸的。就可能需要一些特殊的巧妙方法處理，比如想不到的剪枝優化、優先隊列、A*、dfs 套 bfs，又或者利用一些非常厲害的數學方法比如康託展開 (逆展開) 等等。而今天在這裏，我們談談**雙向 bfs**，體驗一下算法的奧妙！

什麼樣的情況可以使用雙向 bfs 來優化呢? 其實雙向 bfs 的主要思想是問題的拆分吧，比如在一個迷宮中可以往下往右行走，問你有多少種方式從左上到右下。

正常情況下，我們就是搜索遍歷，如果迷宮邊長爲 n，那麼這個複雜度大概是 2^n 級別.

但是實際上我們可以將迷宮拆分一下，比如根據對角線 (比較多)，將迷宮一分爲二。其實你的結果肯定必然經過對角線的這些點對吧！我們只要分別計算出各個對角線各個點的次數然後相加就可以了！

怎麼算？ 就是從 (0,0) 到中間這個點mid的總次數爲n1，然後這個 mid 到 (n,n) 點的總次數爲n2，然後根據排列組合總次數就是n1*n2(n1 和 n2 正常差不多大) 這樣就可以通過乘法減少加法的運算次數啦！

簡單的說，從數據次數來看如果直接搜索全圖經過下圖的那個點的次數爲n1*n2次，如果分成兩個部分相乘那就是n1+n2次。兩者差距如果 n1,n2=1000 左右，那麼這麼一次差距是平方 (根號) 級別的。從搜索圖形來看其實這麼一次搜索是本來一個n*n大小的搜索轉變成 n 次 (每次大概是(n/2)*(n/2)大小的迷宮搜索兩次)。也就是如果 18*18 的迷宮如果使用直接搜索，那麼大概2^18次方量級，而如果採用雙向 bfs，那麼就是2^9這個量級。

例題實戰一下，就拿一道經典雙向 bfs 問題給大家展示一下吧！

題目鏈接：http://oj.hzjingma.com/contest/problem?id=20&pid=8#problem-anchor

分析：對於題目的要求還是很容易理解的，就是找到所有的路徑種類，再判斷其中是對稱路徑的有幾個輸出即可！

對於一個普通思考是這樣的，首先是進行 dfs，然後動態維護一個字符串，每次跑到最後判斷這個路徑字符串是否滿足對稱要求，如果滿足那麼就添加到容器中進行判斷。可惜很遺憾這樣是超時的，僅能通過 40% 的樣例。

接着用普通 bfs 進行嘗試，維護一個 node 節點，每次走的時候路徑儲存起來其實這個效率跟 dfs 差不多依然超時。只能通過 40% 數據。

接下來就開始雙向 bfs 進行分析！

(1) 既然只能右下，那麼對角線的那個位置的肯定是中間的那個字符串的！它的存在不影響是否對稱的 (n*n 的迷宮路徑長度爲n-1 + n爲奇數).

(2) 我們判斷路徑是否對稱，只需要判斷從(1,1)到對角節點k(設爲 k 節點) 的路徑有沒有和從(n,n)到k相同的。如果有路徑相同的那麼就說明這一對構成對稱路徑

(3) 在具體實現上，我們對每個對角線節點可以進行兩次 bfs(一次左上到 (1,1), 一次右下到(n,n)). 並且將路徑放到兩個 hashset(set1,set2) 中，跑完之後用遍歷其中一個 hashset 中的路徑，看看另一個 set 是否存在該路徑，如果存在就說明這個是對稱路徑放到 總的 hashset(set) 中。對角線每個位置都這樣判斷完最後只需要輸出總的 hashset(set) 的集合大小即可！

ac 代碼如下：

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class test2 {    
    static class node{
         int x;
         int y;
        String path="";
        public node() {}
        public node(int x,int y,String team)
        {
            this.x=x;
            this.y=y;
            this.path=team;
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        Set<String>set=new HashSet<String>();//儲存最終結果
        int n=Integer.parseInt(sc.nextLine());
        char map[][]=new char[n][n];
        for(int i=0;i<n;i++)
        {
            String string=sc.nextLine();
            map[i]=string.toCharArray();
        }
        Queue<node>q1=new ArrayDeque<node>();//左上的隊列
        Queue<node>q2=new ArrayDeque<node>();//右下的隊列
        for(int i=0;i<n;i++)
        {
            q1.clear();q2.clear();
            Set<String>set1=new HashSet<String>();//儲存zuoshang
            Set<String>set2=new HashSet<String>();//儲右下
            q1.add(new node(i,n-1-i,""+map[i][n-1-i]));
            q2.add(new node(i,n-1-i,""+map[i][n-1-i]));
            while(!q1.isEmpty()&&!q2.isEmpty())
            {
                node team=q1.poll();
                node team2=q2.poll();
                if(team.x==n-1&&team.y==n-1)//到終點，將路徑儲存
                {
                    //System.out.println(team2.path);   
                    set1.add(team.path);
                    set2.add(team2.path);
                }
                else {
                    if(team.x<n-1)//可以向下
                    {
                        q1.add(new node(team.x+1, team.y, team.path+map[team.x+1][team.y]));
                    }
                    if(team.y<n-1)//可以向右
                    {
                        q1.add(new node(team.x, team.y+1, team.path+map[team.x][team.y+1]));
                    }
                    if(team2.x>0)//上
                    {
                        q2.add(new node(team2.x-1, team2.y, team2.path+map[team2.x-1][team2.y]));
                    }
                    if(team2.y>0)//左
                    {
                        q2.add(new node(team2.x, team2.y-1, team2.path+map[team2.x][team2.y-1]));
                    }
                }

            }
            for(String va:set1)
            {
                if(set2.contains(va))
                {
                    set.add(va);
                }
            }

        }
        System.out.println(set.size());     
    }
}

總結

dfs 和 bfs 是圖論中非常經典的搜索算法，兩種算法的重要程度都非常高，這裏面主要對其簡單介紹，對於普通開發者，能夠用 dfs 和 bfs 能夠解決二叉樹問題、迷宮搜索問題等基礎簡單的就夠了 (面試官不會那麼騷難爲你)。

如果理解比較困難，多看教程、多刷題，多刷題之後每做一題算法跑的大概流程是有個數的。

歡迎關注 「bigsai」

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/CKDGmhy22AEuTuFD9hx27w

猜你喜歡