Dfs、Bfs的終于弄明白了
本文轉(zhuǎn)載自微信公眾號「bigsai」，作者大賽。轉(zhuǎn)載本文請聯(lián)系bigsai公眾號。
前言
你問一個人聽過哪些算法，那么深度優(yōu)先搜索(dfs)和寬度優(yōu)先搜索(bfs)那肯定在其中，很多小老弟學會dfs和bfs就覺得好像懂算法了，無所不能，確實如此，學會dfs和bfs暴力搜索枚舉確實利用計算機超強計算大部分都能求的一份解，學會dfs和bfs去暴力杯混分是一個非常不錯的選擇!
五大經(jīng)典算法的回溯算法其實也是dfs的一種應用，是不是回憶起被折磨的八皇后問題。基礎的dfs和bfs學習來思想很容易，寫出來模板代碼也不難，但很多時候需要在此基礎上靈活變通就有不小難度了。
不過dfs 和bfs初步學習搞懂原理比較簡單，但是想要精通 dfs和bfs還是很難的，因為很多問題是在此基礎上進行變形優(yōu)化的，比如dfs你可能考慮各種剪枝問題，bfs可能會涉及很多貪心的策略，有的還要考慮到記憶化的問題、雙向bfs、bfs+dfs等等才能更好解決的問題，不過本文講的相對基礎，不同的延伸需要自己刷題去學習才行。
鄰接矩陣和鄰接表
dfs和bfs一般用于處理圖論的問題，那么在看問題之前首先要關注圖的存儲問題，正常一般用鄰接矩陣或者鄰接表存儲圖(對于十字鏈表、壓縮矩陣之類空間優(yōu)化這里不進行討論)。
鄰接矩陣：
鄰接矩陣就是用數(shù)組(二維)表示圖，通常這種圖我們會對各個節(jié)點順序的編號，在矩陣內(nèi)數(shù)值表示圖的聯(lián)通情況或者路徑長度。
如果是無權(quán)圖：那么一般用boolean數(shù)組的01表示聯(lián)通性，如果是有權(quán)圖那么數(shù)組的值就用來表示兩者路徑長度，如果為0那么就表示不通。另外如果圖是無向圖那么這個矩陣是對稱的，如果是有向圖那么大概率不是對稱的。
具體可以看下面例子，這種操作方式條理更清晰并且操作方便，當然，這種情況很容易造成空間浪費，所以有人進行空間優(yōu)化，或者是鄰接表的方式存儲圖。
鄰接表：
觀察上面的鄰接矩陣，如果節(jié)點很多但是聯(lián)通路徑很少，那么就浪費了太多的存儲空間，這種情況就更適合鄰接表。
鄰接表一般是數(shù)組套鏈表，比起鄰接矩陣節(jié)省不少空間(直接存儲聯(lián)通信息或者路徑)，在存儲的時候可以根據(jù)數(shù)據(jù)格式要求靈活運用容器(無權(quán)圖省事一些)。
但是正常的無向圖依然會重復浪費一半空間，就有十字鏈表，多重鏈接表等等出現(xiàn)優(yōu)化(大佬們的優(yōu)化是真的牛批)，但在算法邏輯上稍復雜，不過一般圖論算法更注重的是算法的優(yōu)化這里就不介紹十字鏈表等，一個鄰接表存儲的圖可以看下圖：
深度優(yōu)先搜索(dfs)
概念：
深度優(yōu)先搜索屬于圖算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節(jié)點只能訪問一次.
簡單的說，dfs就是在一個圖中按照一個規(guī)則進行搜索，一般基于遞歸實現(xiàn)，對于我們來說dfs就像一個黑魔法一樣，設計好算法它就自動搜索，所以我們要注意的是算法初始化、搜索規(guī)則、結(jié)束條件。二叉樹的前序遍歷就是一個最簡單的dfs遍歷。
我們通常使用鄰接表或者鄰接矩陣儲存圖的信息，這里例子使用鄰接矩陣完成!
對于dfs的流程來說，大致可以認為是這樣：
(1)某個節(jié)點開始先按照一個方向一直遍歷到盡頭，同時標記已經(jīng)走過的點。
(2)遍歷到盡頭后回退到上一個點，同時清除當前點的標記。往下一個方向遍歷一次，然后繼續(xù)重復步驟(1).
(3)一直到所有流程都走完，即回退到起點。
在遍歷的過程中記得需要標記 因為不進行標記會出現(xiàn)死循環(huán)，標記就代表這個點被用過不能用了，而撤回標記就說明這個點又能重新使用了。
舉個例子，例如一個全排列s a i 當s被枚舉到就要標記這個s不能被使用(不可能ssss一直下去吧)，并且遍歷到s a時候a也不能使用，到s a i 時候到盡頭回退 s a 依然要回退s 此時 a和i都被解但是上次指標方向為a(for 循環(huán)到的位置)，那么下一次就要往下個方向i 組成s i,然后在s i a，同理回退到s i,到s，下面兩個方向都被枚舉過所以還要回退到，解放了s a i但是第一個方向s已經(jīng)走過，開始從a 剩下的步驟依次類推就得到了。
不過全排列這是一維空間的dfs運用，在標記時候可以選擇boolean數(shù)組對應位置true標記用過，false表示沒用過。除此之外也可使用動態(tài)數(shù)組List使用過先刪除對應位置元素向下遞歸進行搜索，然后結(jié)束后再對應位置插入也行(不是很推薦，效率比較低)。
對于上面圖片中圖的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++)//查找聯(lián)通節(jié)點
- {
- if(map[index][i]>0&&isVisit[i]==false)
- {
- isVisit[i]=true;
- dfs(i,map);
- }
- }
- System.out.println((index+1)+"訪問結(jié)束 ");
- }
- }
大致順序訪問為
廣度優(yōu)先搜素(bfs)
概念：
BFS，其英文全稱是Breadth First Search。BFS并不使用經(jīng)驗法則算法。從算法的觀點，所有因為展開節(jié)點而得到的子節(jié)點都會被加進一個先進先出的隊列中。一般的實驗里，其鄰居節(jié)點尚未被檢驗過的節(jié)點會被放置在一個被稱為 open 的容器中(例如隊列或是鏈表)，而被檢驗過的節(jié)點則被放置在被稱為 closed 的容器中。(open-closed表)
簡單來說，bfs就是從某個節(jié)點開始按層遍歷，估計大部分人第一次接觸bfs的時候是在學習數(shù)據(jù)結(jié)構(gòu)的二叉樹的層序遍歷!借助一個隊列一層一層遍歷。第二次估計就是在學習圖論的時候，給你一個圖，讓你寫出一個bfs遍歷的順序，此后再無bfs…
如果從路徑上走來看，dfs就是一條跑的很快的瘋狗，到處亂咬，沒路了就跑回來去其他地方繼續(xù)，而bfs就像是一團毒氣，慢慢延伸!
在實現(xiàn)上樸素的bfs就是控制一個隊列，后進先出進行層序遍歷，但很多時候可能有場景需求節(jié)點有權(quán)值可能就需要使用優(yōu)先隊列。
就拿上述的圖來說，我們使用鄰接表來實現(xiàn)一個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比較偏向?qū)崙?zhàn)。
對于dfs和bfs，有些區(qū)別也有些共性，例如在迷宮很多問題dfs能解決bfs也能解決。
對于dfs一般解決的經(jīng)典問題有：
- 二叉樹的搜索遍歷(非層序)
- 經(jīng)典全排列、組合、子集問題
- 回溯算法之八皇后問題
- 迷宮搜索問題(能否找到)
- 其他圖搜索
而bfs一般解決的問題有：
- 二叉樹層序搜索遍歷(各種變形例如分層輸出、之字形等等空間優(yōu)化)
- 無權(quán)圖的最短路徑
- 其他迷宮搜索問題(節(jié)點帶某些權(quán)值的)
- 其他問題
當然這里面羅列不全，dfs關注更多的可能是剪枝問題或者記憶化，剪枝就是剪掉沒必要的搜索，記憶化就是防止太多重復操作。而bfs關注更多的可能是貪心策略選擇(大部分搜索可能有一些附加的條件)可能需要使用優(yōu)先隊列來解決。
然而，當數(shù)據(jù)達到一定程度，我們使用簡單的方法肯定會爆炸的。就可能需要一些特殊的巧妙方法處理，比如想不到的剪枝優(yōu)化、優(yōu)先隊列、A*、dfs套bfs，又或者利用一些非常厲害的數(shù)學方法比如康托展開(逆展開)等等。而今天在這里，我們談談雙向bfs，體驗一下算法的奧妙!
什么樣的情況可以使用雙向bfs來優(yōu)化呢?其實雙向bfs的主要思想是問題的拆分吧，比如在一個迷宮中可以往下往右行走，問你有多少種方式從左上到右下。
正常情況下，我們就是搜索遍歷，如果迷宮邊長為n，那么這個復雜度大概是2^n級別.
但是實際上我們可以將迷宮拆分一下，比如根據(jù)對角線(比較多)，將迷宮一分為二。其實你的結(jié)果肯定必然經(jīng)過對角線的這些點對吧!我們只要分別計算出各個對角線各個點的次數(shù)然后相加就可以了!
怎么算? 就是從(0,0)到中間這個點mid的總次數(shù)為n1，然后這個mid到(n,n)點的總次數(shù)為n2，然后根據(jù)排列組合總次數(shù)就是n1*n2(n1和n2正常差不多大)這樣就可以通過乘法減少加法的運算次數(shù)啦!
簡單的說，從數(shù)據(jù)次數(shù)來看如果直接搜索全圖經(jīng)過下圖的那個點的次數(shù)為n1*n2次，如果分成兩個部分相乘那就是n1+n2次。兩者差距如果n1,n2=1000左右，那么這么一次差距是平方(根號)級別的。從搜索圖形來看其實這么一次搜索是本來一個n*n大小的搜索轉(zhuǎn)變成n次(每次大概是(n/2)*(n/2)大小的迷宮搜索兩次)。也就是如果18*18的迷宮如果使用直接搜索，那么大概2^18次方量級，而如果采用雙向bfs，那么就是2^9這個量級。
例題實戰(zhàn)一下，就拿一道經(jīng)典雙向bfs問題給大家展示一下吧!
題目鏈接：http://oj.hzjingma.com/contest/problem?id=20&pid=8#problem-anchor
分析：對于題目的要求還是很容易理解的，就是找到所有的路徑種類，再判斷其中是對稱路徑的有幾個輸出即可!
對于一個普通思考是這樣的，首先是進行dfs，然后動態(tài)維護一個字符串，每次跑到最后判斷這個路徑字符串是否滿足對稱要求，如果滿足那么就添加到容器中進行判斷。可惜很遺憾這樣是超時的，僅能通過40%的樣例。
接著用普通bfs進行嘗試，維護一個node節(jié)點，每次走的時候路徑儲存起來其實這個效率跟dfs差不多依然超時。只能通過40%數(shù)據(jù)。
接下來就開始雙向bfs進行分析!
(1) 既然只能右下，那么對角線的那個位置的肯定是中間的那個字符串的!它的存在不影響是否對稱的(n*n的迷宮路徑長度為n-1 + n為奇數(shù)).
(2) 我們判斷路徑是否對稱，只需要判斷從(1,1)到對角節(jié)點k(設為k節(jié)點)的路徑有沒有和從(n,n)到k相同的。如果有路徑相同的那么就說明這一對構(gòu)成對稱路徑
(3) 在具體實現(xiàn)上，我們對每個對角線節(jié)點可以進行兩次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>();//儲存最終結(jié)果
- 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());
- }
- }
總結(jié)
dfs和bfs是圖論中非常經(jīng)典的搜索算法，兩種算法的重要程度都非常高，這里面主要對其簡單介紹，對于普通開發(fā)者，能夠用dfs和bfs能夠解決二叉樹問題、迷宮搜索問題等基礎簡單的就夠了(面試官不會那么騷難為你)。
如果理解比較困難，多看教程、多刷題，多刷題之后每做一題算法跑的大概流程是有個數(shù)的。
