文章出處：極客時(shí)間《數(shù)據(jù)結(jié)構(gòu)和算法之美》-作者：王爭(zhēng)。該系列文章是本人的學(xué)習(xí)筆記。

搜索算法

算法是作用于數(shù)據(jù)結(jié)構(gòu)之上的。深度優(yōu)先搜索、廣度優(yōu)先搜索是作用于圖這種數(shù)據(jù)結(jié)構(gòu)之上的。圖上的搜索算法可以理解為從一個(gè)頂點(diǎn)到另外一個(gè)頂點(diǎn)。

常用的搜索算法有：暴力的深度優(yōu)先搜索、廣度優(yōu)先搜索，還有A*、IDA*等啟發(fā)式搜索。

實(shí)際應(yīng)用舉例

在社交網(wǎng)絡(luò)中有六度分隔理論，就是一個(gè)人最多通過(guò)六個(gè)人可以認(rèn)識(shí)另外一個(gè)人。一個(gè)用戶的一度好友就是他的好友，二度好友是他好友的好友，以此類推。給你一個(gè)關(guān)系圖，你可以找到一個(gè)用戶的三度好友嗎？

廣度優(yōu)先搜索(BFS)

BFS:先找離起始頂點(diǎn)最近的點(diǎn)，然后是次近，依次向外搜索。

下面的代碼是無(wú)向圖的BFS代碼。

/*** 無(wú)向圖*/ public class UnDirectedGraph {private int v;//頂點(diǎn)個(gè)數(shù)private LinkedList<Integer> adj[];//鄰接表public UnDirectedGraph(int v){this.v = v;this.adj = new LinkedList[v];for(int i=0;i<v;i++){this.adj[i] = new LinkedList<>();}}public void addEdge(int s,int t){this.adj[s].add(t);this.adj[t].add(s);}/*** 廣度優(yōu)先搜索從s節(jié)點(diǎn)到t節(jié)點(diǎn):打印從s到t的節(jié)點(diǎn)路徑* @param s* @param t*/public void bfs(int s, int t) {if(s==t){System.out.println(s);return;}Queue<Integer> queue = new LinkedList<>();queue.offer(s);boolean[] visited = new boolean[this.v];visited[s] = true;int[] pre = new int[v];Arrays.fill(pre,-1);while(!queue.isEmpty()){int size = queue.size();for(int i =0;i<size;i++){//每一層int w = queue.poll();for(int j =0;j<this.adj[w].size();j++){int q = this.adj[w].get(j);if(!visited[q]){pre[q] = w;if(q==t){printPath(pre,s,t);return;}visited[q]=true;queue.offer(q);}}}}}private void printPath(int[] pre,int s,int t) {if(s!=t && pre[t]!=-1){printPath(pre,s,pre[t]);}System.out.print(t+"\t");} }

這里三個(gè)重要的臨時(shí)變量queue、visited、pre。
queue：是一個(gè)隊(duì)列，存儲(chǔ)已經(jīng)被訪問(wèn)，但是鄰接點(diǎn)還沒(méi)有被訪問(wèn)的節(jié)點(diǎn)。
visited：記錄已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，防止重復(fù)訪問(wèn)。
pre：記錄從哪個(gè)節(jié)點(diǎn)可以達(dá)到下標(biāo)所表示的節(jié)點(diǎn)。pre[w]記錄從哪個(gè)節(jié)點(diǎn)達(dá)到w節(jié)點(diǎn) 。

時(shí)間復(fù)雜度分析：BFS中每個(gè)節(jié)點(diǎn)都會(huì)被訪問(wèn)一次，入隊(duì)一次，每條邊都會(huì)被訪問(wèn)一次，時(shí)間復(fù)雜度O(V+E)。V表示頂點(diǎn)個(gè)數(shù)，E表示邊的個(gè)數(shù)。

空間復(fù)雜度分析：臨時(shí)變量queue、visited、pre的個(gè)數(shù)都不會(huì)超過(guò)頂點(diǎn)個(gè)數(shù)。所以上O(V)。

上面的代碼可以抽象出BFS代碼的框架。

深度優(yōu)先搜索(DFS)

DFS：DFS是從起始頂點(diǎn)開(kāi)始，按照一條路徑一直走到終點(diǎn)t或者不能再走下去。然后返回到上一個(gè)可選擇的狀態(tài)，選擇另外一條路徑，繼續(xù)走。DFS是一種非常有名的算法思想：回溯。

下圖中實(shí)現(xiàn)代表搜索路徑，虛線代表回退。

private boolean found = false;public void dfs(int s, int t) {boolean[] visited = new boolean[this.v];int[] pre = new int[v];Arrays.fill(pre,-1);dfs(s,t,visited,pre);printPath(pre,s,t);}private void dfs(int w, int t, boolean[] visited, int[] pre) {if(w==t){found = true;return;}visited[w] = true;if(!found){for(int j =0;j<this.adj[w].size() && !found;j++){int q = this.adj[w].get(j);if(!visited[q]) {pre[q] = w;visited[q]=true;dfs(q,t,visited,pre);}}}}

時(shí)間復(fù)雜度分析：從圖中看每條邊最多被訪問(wèn)2次，一次搜索，一次回退。時(shí)間復(fù)雜度O(E)。

空間復(fù)雜度分析：消耗內(nèi)存主要是 visited、prev 數(shù)組和遞歸調(diào)用棧。visited、prev 數(shù)組和頂點(diǎn)個(gè)數(shù)相同。遞歸調(diào)用不會(huì)超過(guò)頂點(diǎn)的個(gè)數(shù)。所以空間復(fù)雜度O(V)。

適用范圍

DFS和BFS搜索的空間復(fù)雜度都是O(V),當(dāng)頂點(diǎn)個(gè)數(shù)很大的時(shí)候，就不適合這兩種算法。

三度好友

上面提到的查找一個(gè)人的三度好友適合用BFS。一層一層向外搜索。找到第三層。

總結(jié)

以上是生活随笔為你收集整理的算法十——深度优先搜索和广度优先搜索的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。