31|深度和廣度優(yōu)先搜索:如何找出社交網(wǎng)絡中的三度好友關(guān)系?
總結(jié)
對于這兩個搜索方法锣笨，其實我們是可以輕松的看出來崔梗，他們有許多差異與許多相同點的涂乌。
1.數(shù)據(jù)結(jié)構(gòu)上的運用
DFS用遞歸的形式械筛，用到了棧結(jié)構(gòu)敢艰，先進后出舵匾。
BFS選取狀態(tài)用隊列的形式俊抵，先進先出。
2.復雜度
DFS的復雜度與BFS的復雜度大體一致坐梯，不同之處在于遍歷的方式與對于問題的解決出發(fā)點不同徽诲，DFS適合目標明確，而BFS適合大范圍的尋找吵血。
3.思想
思想上來說這兩種方法都是窮竭列舉所有的情況谎替。
廣度優(yōu)先搜索(BFS)
廣度優(yōu)先搜索(Breadth-First-Search)，我們平常都把簡稱為BFS蹋辅。直觀地講钱贯，它其實就是一種“地 毯式”層層推進的搜索策略，即先查找離起始頂點最近的侦另，然后是次近的秩命，依次往外搜索。理解起來 并不難淋肾，所以我畫了一張示意圖硫麻，你可以看下。
盡管廣度優(yōu)先搜索的原理挺簡單樊卓，但代碼實現(xiàn)還是稍微有點復雜度拿愧。所以，我們重點講一下它的代 碼實現(xiàn)碌尔。 這里面浇辜，bfs()函數(shù)就是基于之前定義的券敌，圖的廣度優(yōu)先搜索的代碼實現(xiàn)。其中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 + " ");
}
這段代碼不是很好理解，里面有三個重要的輔助變量visited绪囱、queue测蹲、prev。只要理解這三個變量鬼吵， 讀懂這段代碼估計就沒什么問題了扣甲。 visited是用來記錄已經(jīng)被訪問的頂點，用來避免頂點被重復訪問齿椅。如果頂點q被訪問琉挖，那相應的 visited[q]會被設置為true。 queue是一個隊列涣脚，用來存儲已經(jīng)被訪問示辈、但相連的頂點還沒有被訪問的頂點。因為廣度優(yōu)先搜索 是逐層訪問的遣蚀，也就是說顽耳，我們只有把第k層的頂點都訪問完成之后，才能訪問第k+1層的頂點妙同。當 我們訪問到第k層的頂點的時候，我們需要把第k層的頂點記錄下來膝迎，稍后才能通過第k層的頂點來找 第k+1層的頂點粥帚。所以，我們用這個隊列來實現(xiàn)記錄的功能限次。 prev用來記錄搜索路徑芒涡。當我們從頂點s開始，廣度優(yōu)先搜索到頂點t后卖漫，prev數(shù)組中存儲的就是搜 索的路徑费尽。不過，這個路徑是反向存儲的羊始。prev[w]存儲的是旱幼，頂點w是從哪個前驅(qū)頂點遍歷過來 的。比如突委，我們通過頂點2的鄰接表訪問到頂點3柏卤，那prev[3]就等于2冬三。為了正向打印出路徑，我們 需要遞歸地來打印缘缚，你可以看下print()函數(shù)的實現(xiàn)方式勾笆。 為了方便你理解，我畫了一個廣度優(yōu)先搜索的分解圖桥滨，你可以結(jié)合著代碼以及我的講解一塊兒看窝爪。
掌握了廣優(yōu)先搜索算法的原理，我們來看下齐媒，廣度優(yōu)先搜索的時間蒲每、空間復雜度是多少呢？
最壞情況下里初，終止頂點 t 離起始頂點 s 很遠啃勉，需要遍歷完整個圖才能找到。這個時候双妨，每個頂點都要進出一遍隊列淮阐，每個邊也都會被訪問一次，所以刁品，廣度優(yōu)先搜索的時間復雜度是 O(V+E)泣特，其中，V 表示頂點的個數(shù)挑随，E 表示邊的個數(shù)状您。當然，對于一個連通圖來說兜挨，也就是說一個圖中的所有頂點都是連通的膏孟，E 肯定要大于等于 V-1，所以拌汇，廣度優(yōu)先搜索的時間復雜度也可以簡寫為 O(E)柒桑。
廣度優(yōu)先搜索的空間消耗主要在幾個輔助變量 visited 數(shù)組、queue 隊列噪舀、prev 數(shù)組上魁淳。這三個存儲空間的大小都不會超過頂點的個數(shù)，所以空間復雜度是 O(V)与倡。
深度優(yōu)先搜索（DFS）
深度優(yōu)先搜索（Depth-First-Search）界逛，簡稱 DFS。最直觀的例子就是“走迷宮”纺座。
假設你站在迷宮的某個岔路口息拜，然后想找到出口。你隨意選擇一個岔路口來走，走著走著發(fā)現(xiàn)走不通的時候该溯，你就回退到上一個岔路口岛抄，重新選擇一條路繼續(xù)走，直到最終找到出口狈茉。這種走法就是一種深度優(yōu)先搜索策略夫椭。
走迷宮的例子很容易能看懂，我們現(xiàn)在再來看下氯庆，如何在圖中應用深度優(yōu)先搜索蹭秋，來找某個頂點到另一個頂點的路徑。
你可以看我畫的這幅圖堤撵。搜索的起始頂點是 s仁讨，終止頂點是 t，我們希望在圖中尋找一條從頂點 s 到頂點 t 的路徑实昨。如果映射到迷宮那個例子洞豁，s 就是你起始所在的位置，t 就是出口荒给。
我用深度遞歸算法丈挟，把整個搜索的路徑標記出來了。這里面實線箭頭表示遍歷志电，虛線箭頭表示回退曙咽。從圖中我們可以看出，深度優(yōu)先搜索找出來的路徑挑辆，并不是頂點 s 到頂點 t 的最短路徑例朱。
實際上，深度優(yōu)先搜索用的是一種比較著名的算法思想鱼蝉，回溯思想洒嗤。這種思想解決問題的過程，非常適合用遞歸來實現(xiàn)魁亦∷附撸回溯思想我們后面會有專門的一節(jié)來講，我們現(xiàn)在還回到深度優(yōu)先搜索算法上吉挣。
我把上面的過程用遞歸來翻譯出來，就是下面這個樣子婉弹。我們發(fā)現(xiàn)睬魂，深度優(yōu)先搜索代碼實現(xiàn)也用到了 prev、visited 變量以及 print() 函數(shù)镀赌，它們跟廣度優(yōu)先搜索代碼實現(xiàn)里的作用是一樣的氯哮。不過，深度優(yōu)先搜索代碼實現(xiàn)里商佛，有個比較特殊的變量 found喉钢，它的作用是姆打，當我們已經(jīng)找到終止頂點 t 之后，我們就不再遞歸地繼續(xù)查找了肠虽。
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);
}
}
}
理解了深度優(yōu)先搜索算法之后幔戏，我們來看，深度度優(yōu)先搜索的時税课、空間間復雜度是多少呢? 從我前面畫的圖可以看出闲延，每條邊最多會被訪問兩次，一次是遍歷韩玩，一次是回退垒玲。所以，圖上的深 度優(yōu)先搜索算法的時間復雜度是O(E)找颓，E表示邊的個數(shù)合愈。 深度優(yōu)先搜索算法的消耗內(nèi)存主要是visited、prev數(shù)組和遞歸調(diào)用棧击狮。visited佛析、prev數(shù)組的大小跟頂 點的個數(shù)V成正比，遞歸調(diào)用棧的最大深度不會超過頂點的個數(shù)帘不，所以總的空間復雜度就是O(V)说莫。
解答開篇
了解了深度優(yōu)先搜索和廣度優(yōu)先搜索的原理之后，開篇的問題是不是變得很簡單了呢?我們現(xiàn)在來 一起看下寞焙，如何找出社交網(wǎng)絡中某個用戶的三度好友關(guān)系? 上一節(jié)我們講過储狭，社交網(wǎng)絡可以用圖來表示。這個問題就非常適合用圖的廣度優(yōu)先搜索算法來解 決捣郊，因為廣度優(yōu)先搜索是層層往外推進的辽狈。首先，遍歷與起始頂點最近的一層頂點呛牲，也就是用戶的 一度好友刮萌，然后再遍歷與用戶距離的邊數(shù)為2的頂點，也就是二度好友關(guān)系娘扩，以及與用戶距離的邊 數(shù)為3的頂點着茸，也就是三度好友關(guān)系。 我們只需要稍加改造一下廣度優(yōu)先搜索代碼琐旁，用一個數(shù)組來記錄每個頂點與起始頂點的距離涮阔，非常 容易就可以找出三度好友關(guān)系。
內(nèi)容小結(jié)
廣度優(yōu)先搜索和深度優(yōu)先搜索是圖上的兩種最常用灰殴、最基本的搜索算法敬特，比起其他高級的搜索算 法，比如A、IDA等伟阔，要簡單粗暴辣之，沒有什么優(yōu)化，所以皱炉，也被叫作暴力搜索算法怀估。所以，這兩種 搜索算法僅適用于狀態(tài)空間不大娃承，也就是說圖不大的搜索奏夫。 廣度優(yōu)先搜索，通俗的理解就是历筝，地毯式層層推進酗昼，從起始頂點開始，依次往外遍歷梳猪。廣度優(yōu)先搜 索需要借助隊列來實現(xiàn)麻削，遍歷得到的路徑就是，起始頂點到終止頂點的最短路徑春弥。深度優(yōu)先搜索用 的是回溯思想呛哟，非常適合用遞歸實現(xiàn)。換種說法匿沛，深度優(yōu)先搜索是借助棧來實現(xiàn)的扫责。在執(zhí)行效率方 面，深度優(yōu)先和廣度優(yōu)先搜索的時間復雜度都是O(E)逃呼，空間復雜度是O(V)鳖孤。
課后思考
我們通過廣度優(yōu)先搜索算法解決了開篇的問題，你可以思考一下抡笼，能否用深度優(yōu)先搜索來解決呢? 學習數(shù)據(jù)結(jié)構(gòu)最難的不是理解和掌握原理苏揣，而是能靈活地將各種場景和問題抽象成對應的數(shù)據(jù)結(jié)構(gòu) 和算法。今天的內(nèi)容中提到推姻，迷宮可以抽象成圖平匈，走迷宮可以抽象成搜索算法，你能具體講講藏古，如 何將迷宮抽象成一個圖嗎?或者換個說法增炭，如何在計算機中存儲一個迷宮? 歡迎留言和我分享，也歡迎點擊“請朋友讀”拧晕，把今天的內(nèi)容分享給你的好友隙姿，和他一起討論、學 習防症。
答：DFS遞歸時傳多一個離初始節(jié)點的距離值，訪問節(jié)點時，距離超過3的不再繼續(xù)遞歸
學習數(shù)據(jù)結(jié)構(gòu)最難的不是理解和掌握原理蔫敲，而是能靈活地將各種場景和問題抽象成對應的數(shù)據(jù)結(jié)構(gòu)和算法饲嗽。今天的內(nèi)存中提到，迷宮可以抽象成圖奈嘿，走迷宮可以抽象成搜索算法貌虾，如何將迷宮抽象成一個圖？如何在計算機中存儲一個迷宮裙犹？
答：初始化兩個頂點為迷宮起點和終點尽狠，從起點開始，遇到分叉點叶圃，為每個分支都新建一個節(jié)點袄膏，并和前一節(jié)點連接，遞歸每個分支直到終點
