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