在有向圖和無向圖中，如果 節(jié)點之間無權值或者權值相等 ，那么 dfs和bfs 時常出現(xiàn)在日常算法中。不僅如此， dfs，bfs不僅僅能夠解決圖論的問題 ，在其他問題的搜索上也是 最基礎(但是 策略不同 )的 兩種經(jīng)典算法 。
并且五大經(jīng)典算法的 回溯算法 其實也是 dfs
的一種。dfs,bfs基礎能夠解決搜索類問題的大部分情況，只不過搜索隨著數(shù)據(jù)增大而呈非線性的增長，所以兩種算法在數(shù)據(jù)較多的情況是不太適用的。
鄰接矩陣和鄰接表
鄰接矩陣：鄰接矩陣就是用數(shù)組(二維)表示圖。具體可以看下面例子。當然， 這種情況很容易造成空間浪費 ，所以很多人進行空間優(yōu)化，甚至是鄰接表的方式。
鄰接表： 而鄰接表則是數(shù)組套鏈表。這樣可以比起鄰接矩陣節(jié)省不少空間，但是如果無向圖 依然會重復浪費一半空間 ，就有十字鏈表，多重鏈接表等等出現(xiàn)。同時，對于有權圖來說， 只需對節(jié)點加一個屬性weight即可！
深度優(yōu)先搜索(dfs)
概念：
深度優(yōu)先搜索屬于圖算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節(jié)點只能訪問一次.
簡單的說，要完成dfs要有前提條件.就是有 聯(lián)通點 。單個節(jié)點dfs就斷掉了，他要找打和它聯(lián)系的節(jié)點。dfs入手可能比bfs簡單的原因是 dfs大部分之間利用遞歸的走向完成dfs ，而 很少需要標記 。
我們通常使用 鄰接表(一維數(shù)組套鏈表a[List]) 或者 鄰接矩陣(二維數(shù)組a[][]) 儲存圖的信息。有時為了優(yōu)化空間會選擇 十字鏈表 或者 鄰接多重表 進行存儲節(jié)省空間，但是操作往往是很復雜的。并且一般來說圖的 更大需要設計算法的優(yōu)化 ，所以這里例子使用 鄰接矩陣 完成！
對于dfs的流程來說，大致可以認為是這樣：
- 從初始點開始按照一個方向遍歷，這個方向到盡頭停止后到另一個方向，，，直到所有操作完成退出！
- 深度優(yōu)先搜索執(zhí)行過程像是一個棧的操作。 喜新厭舊 。總是處理最新加入的節(jié)點，這點遞歸恰好滿足其性質(zhì)，并且遞歸代碼 寫起來也更簡潔 。
- dfs的流程可以 參考二叉樹的前序遍歷 ，它實質(zhì)就是一個dfs。
對于上圖的dfs。可以用一下代碼來表示：
package 圖論;
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)+"訪問結束 ");
}
}
復制代碼
大致順序訪問為
寬度(廣度)優(yōu)先搜索(bfs)
概念：
BFS，其英文全稱是Breadth First Search。 BFS并不使用經(jīng)驗法則算法。從算法的觀點，所有因為展開節(jié)點而得到的子節(jié)點都會被加進一個先進先出的隊列中。一般的實驗里，其鄰居節(jié)點尚未被檢驗過的節(jié)點會被放置在一個被稱為 open 的容器中（例如隊列或是鏈表），而被檢驗過的節(jié)點則被放置在被稱為 closed 的容器中。（open-closed表）
簡單來說，bfs就是先進先出的隊列遍歷，然而這樣在分布的情況就是 按層遍歷 ，可以參考二叉樹遍歷的 層序遍歷 ！
如果從路徑上走來看， dfs就是一條跑的很快的瘋狗 ，到處亂咬。沒路了就轉(zhuǎn)頭，再沒路了再跑回來去其他地方， 而bfs就像是一團毒氣 ，慢慢延申！
就拿上述的圖來說，我們使用鄰接表來實現(xiàn)遍歷。
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往往是在 尋路上的兩個極端的表現(xiàn) ！當然在不同場景使用可能也有些不同。
- dfs可以運用在查找和爬蟲中，如果爬蟲的話那么更多是優(yōu)先找到不同鏈接，可用于統(tǒng)計等。而在查找中比如 迷宮類 可以利用dfs判斷 是否存在路徑，出路 等等。
- bfs也可以運用在算法和爬蟲之中。而bfs優(yōu)先處理自己周圍的資源。所以在爬蟲可以用于遍歷網(wǎng)站，搜尋整個網(wǎng)站的價值信息等等，筆者以前用 爬蟲+bfs實現(xiàn)過下載網(wǎng)站的模板 (17素材的網(wǎng)頁模板)。而在算法中， 在迷宮或者無權圖中 ， bfs可以找到最短路徑 。
在上面可以看得出在鄰接矩陣實現(xiàn)儲存上 浪費很多空間 ，但有些情況使用二維數(shù)組很合適—— 迷宮類問題 。我們在面試學習，會經(jīng)常遇到迷宮類需要bfs找最短路徑，或者dfs查詢是否存在。或者雙bfs又或者dfs+bfs等等解決具體問題。
