加關注可以第一時間接收數據結構系列文章，覺得不錯可以轉發和點贊，謝謝支持
上一節我們講了圖的表示方法，講到如何用有向圖、無向圖來表示一個社交網絡。在社交網絡中，有一個六度分割理論，具體是說，你與世界上的另一個人間隔的關係不會超過六度，也就是說平均只需要六步就可以聯繫到任何兩個互不相識的人。
一個用戶的一度連接用戶很好理解，就是他的好友，二度連接用戶就是他好友的好友，三度連接用戶就是他好友的好友的好友。在社交網絡中，我們往往通過用戶之間的連接關係，來實現推薦“可能認識的人”這麼一個功能。今天的開篇問題就是，給你一個用戶，如何找出這個用戶的所有三度（其中包含一度、二度和三度）好友關係？
這就要用到今天要講的深度優先和廣度優先搜索算法。
什麼是“搜索”算法？
我們知道，算法是作用於具體數據結構之上的，深度優先搜索算法和廣度優先搜索算法都是基於“圖”這種數據結構的。這是因為，圖這種數據結構的表達能力很強，大部分涉及搜索的場景都可以抽象成“圖”。
圖上的搜索算法，最直接的理解就是，在圖中找出從一個頂點出發，到另一個頂點的路徑。具體方法有很多，比如今天要講的兩種最簡單、最“暴力”的深度優先、廣度優先搜索，還有 A*、IDA* 等啟發式搜索算法。
我們上一節講過，圖有兩種主要存儲方法，鄰接表和鄰接矩陣。今天我會用鄰接表來存儲圖。
我這裡先給出圖的代碼實現。需要說明一下，深度優先搜索算法和廣度優先搜索算法，既可以用在無向圖，也可以用在有向圖上。在今天的講解中，我都針對無向圖來講解。
public class Graph { // 無向圖
private int v; // 頂點的個數
private LinkedList<integer> adj[]; // 鄰接表
public Graph(int v) {
this.v = v;
adj = new LinkedList[v];
for (int i=0; iadj[i] = new LinkedList<>();
}
}
public void addEdge(int s, int t) { // 無向圖一條邊存兩次
adj[s].add(t);
adj[t].add(s);
}
}
/<integer>廣度優先搜索（BFS）
廣度優先搜索（Breadth-First-Search），我們平常都把簡稱為 BFS。直觀地講，它其實就是一種“地毯式”層層推進的搜索策略，即先查找離起始頂點最近的，然後是次近的，依次往外搜索。理解起來並不難，所以我畫了一張示意圖，你可以看下。
儘管廣度優先搜索的原理挺簡單，但代碼實現還是稍微有點複雜度。所以，我們重點講一下它的代碼實現。
這裡面，bfs() 函數就是基於之前定義的，圖的廣度優先搜索的代碼實現。其中 s 表示起始頂點，t 表示終止頂點。我們搜索一條從 s 到 t 的路徑。實際上，這樣求得的路徑就是從 s 到 t 的最短路徑。
public void bfs(int s, int t) {
if (s == t) return;
boolean[] visited = new boolean[v];
visited[s]=true;
Queue<integer> queue = new LinkedList<>();
queue.add(s);
int[] prev = new int[v];
for (int i = 0; i < v; ++i) {
prev[i] = -1;
}
while (queue.size() != 0) {
int w = queue.poll();
for (int i = 0; i < adj[w].size(); ++i) {
int q = adj[w].get(i);
if (!visited[q]) {
prev[q] = w;
if (q == t) {
print(prev, s, t);
return;
}
visited[q] = true;
queue.add(q);
}
}
}
}
private void print(int[] prev, int s, int t) { // 遞歸打印 s->t 的路徑
if (prev[t] != -1 && t != s) {
print(prev, s, prev[t]);
}
System.out.print(t + " ");
}
/<integer>這段代碼不是很好理解，裡面有三個重要的輔助變量 visited、queue、prev。只要理解這三個變量，讀懂這段代碼估計就沒什麼問題了。
visited是用來記錄已經被訪問的頂點，用來避免頂點被重複訪問。如果頂點 q 被訪問，那相應的 visited[q] 會被設置為 true。
queue是一個隊列，用來存儲已經被訪問、但相連的頂點還沒有被訪問的頂點。因為廣度優先搜索是逐層訪問的，也就是說，我們只有把第 k 層的頂點都訪問完成之後，才能訪問第 k+1 層的頂點。當我們訪問到第 k 層的頂點的時候，我們需要把第 k 層的頂點記錄下來，稍後才能通過第 k 層的頂點來找第 k+1 層的頂點。所以，我們用這個隊列來實現記錄的功能。
prev用來記錄搜索路徑。當我們從頂點 s 開始，廣度優先搜索到頂點 t 後，prev 數組中存儲的就是搜索的路徑。不過，這個路徑是反向存儲的。prev[w] 存儲的是，頂點 w 是從哪個前驅頂點遍歷過來的。比如，我們通過頂點 2 的鄰接表訪問到頂點 3，那 prev[3] 就等於 2。為了正向打印出路徑，我們需要遞歸地來打印，你可以看下 print() 函數的實現方式。
為了方便你理解，我畫了一個廣度優先搜索的分解圖，你可以結合著代碼以及我的講解一塊兒看。
掌握了廣優先搜索算法的原理，我們來看下，廣度優先搜索的時間、空間複雜度是多少呢？
最壞情況下，終止頂點 t 離起始頂點 s 很遠，需要遍歷完整個圖才能找到。這個時候，每個頂點都要進出一遍隊列，每個邊也都會被訪問一次，所以，廣度優先搜索的時間複雜度是 O(V+E)，其中，V 表示頂點的個數，E 表示邊的個數。當然，對於一個連通圖來說，也就是說一個圖中的所有頂點都是連通的，E 肯定要大於等於 V-1，所以，廣度優先搜索的時間複雜度也可以簡寫為 O(E)。
廣度優先搜索的空間消耗主要在幾個輔助變量 visited 數組、queue 隊列、prev 數組上。這三個存儲空間的大小都不會超過頂點的個數，所以空間複雜度是 O(V)。
深度優先搜索（DFS）
深度優先搜索（Depth-First-Search），簡稱 DFS。最直觀的例子就是“走迷宮”。
假設你站在迷宮的某個岔路口，然後想找到出口。你隨意選擇一個岔路口來走，走著走著發現走不通的時候，你就回退到上一個岔路口，重新選擇一條路繼續走，直到最終找到出口。這種走法就是一種深度優先搜索策略。
走迷宮的例子很容易能看懂，我們現在再來看下，如何在圖中應用深度優先搜索，來找某個頂點到另一個頂點的路徑。
你可以看我畫的這幅圖。搜索的起始頂點是 s，終止頂點是 t，我們希望在圖中尋找一條從頂點 s 到頂點 t 的路徑。如果映射到迷宮那個例子，s 就是你起始所在的位置，t 就是出口。
我用深度遞歸算法，把整個搜索的路徑標記出來了。這裡面實線箭頭表示遍歷，虛線箭頭表示回退。從圖中我們可以看出，深度優先搜索找出來的路徑，並不是頂點 s 到頂點 t 的最短路徑。
實際上，深度優先搜索用的是一種比較著名的算法思想，回溯思想。這種思想解決問題的過程，非常適合用遞歸來實現。回溯思想我們後面會有專門的一節來講，我們現在還回到深度優先搜索算法上。
我把上面的過程用遞歸來翻譯出來，就是下面這個樣子。我們發現，深度優先搜索代碼實現也用到了 prev、visited 變量以及 print() 函數，它們跟廣度優先搜索代碼實現裡的作用是一樣的。不過，深度優先搜索代碼實現裡，有個比較特殊的變量 found，它的作用是，當我們已經找到終止頂點 t 之後，我們就不再遞歸地繼續查找了。
boolean found = false; // 全局變量或者類成員變量
public void dfs(int s, int t) {
found = false;
boolean[] visited = new boolean[v];
int[] prev = new int[v];
for (int i = 0; i < v; ++i) {
prev[i] = -1;
}
recurDfs(s, t, visited, prev);
print(prev, s, t);
}
private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
if (found == true) return;
visited[w] = true;
if (w == t) {
found = true;
return;
}
for (int i = 0; i < adj[w].size(); ++i) {
int q = adj[w].get(i);
if (!visited[q]) {
prev[q] = w;
recurDfs(q, t, visited, prev);
}
}
}
理解了深度優先搜索算法之後，我們來看，深度度優先搜索的時、空間間複雜度是多少呢？
從我前面畫的圖可以看出，每條邊最多會被訪問兩次，一次是遍歷，一次是回退。所以，圖上的深度優先搜索算法的時間複雜度是 O(E)，E 表示邊的個數。
深度優先搜索算法的消耗內存主要是 visited、prev 數組和遞歸調用棧。visited、prev 數組的大小跟頂點的個數 V 成正比，遞歸調用棧的最大深度不會超過頂點的個數，所以總的空間複雜度就是 O(V)。
解答開篇
瞭解了深度優先搜索和廣度優先搜索的原理之後，開篇的問題是不是變得很簡單了呢？我們現在來一起看下，如何找出社交網絡中某個用戶的三度好友關係？
上一節我們講過，社交網絡可以用圖來表示。這個問題就非常適合用圖的廣度優先搜索算法來解決，因為廣度優先搜索是層層往外推進的。首先，遍歷與起始頂點最近的一層頂點，也就是用戶的一度好友，然後再遍歷與用戶距離的邊數為 2 的頂點，也就是二度好友關係，以及與用戶距離的邊數為 3 的頂點，也就是三度好友關係。
我們只需要稍加改造一下廣度優先搜索代碼，用一個數組來記錄每個頂點與起始頂點的距離，非常容易就可以找出三度好友關係。
內容小結
廣度優先搜索和深度優先搜索是圖上的兩種最常用、最基本的搜索算法，比起其他高級的搜索算法，比如 A*、IDA* 等，要簡單粗暴，沒有什麼優化，所以，也被叫作暴力搜索算法。所以，這兩種搜索算法僅適用於狀態空間不大，也就是說圖不大的搜索。
廣度優先搜索，通俗的理解就是，地毯式層層推進，從起始頂點開始，依次往外遍歷。廣度優先搜索需要藉助隊列來實現，遍歷得到的路徑就是，起始頂點到終止頂點的最短路徑。深度優先搜索用的是回溯思想，非常適合用遞歸實現。換種說法，深度優先搜索是藉助棧來實現的。在執行效率方面，深度優先和廣度優先搜索的時間複雜度都是 O(E)，空間複雜度是 O(V)。
閱讀更多 xiuxiuing 的文章
