一文理解搜索演算法-徹底入門DFS

最新 08-07

閱讀文本大概需要 3.6 分鐘。

前言

搜索是一種適用性非常廣泛的演算法。很多我們實際遇到的問題，數據量可能不會太大，都可以暴力搜索一把來解決。

其實這個演算法網上也很多但是都講的比較複雜很多人也只能看一個前面的東西後面的其實看不懂。也有很多文章講的不是太精鍊，講不出個所以然來。所以小編今天就利用這篇文章來帶大家先入門搜索演算法。最簡單的 DFS 相當於一個暴力搜索演算法。

如果不了解暴力的可以看看前面寫的這篇文章：

基本上遇到的很多題目暴力都能解決，畢竟 CPU 處理的速度這麼快。

搜索DFS正文

搜索演算法是屬於一種比較基礎的演算法，相當於萬丈高樓的第一層，也是後期學習的一些高級演算法的基礎部分,搜索演算法分為深度優先搜索（ Depth First Search , DFS）和廣度優先搜索（Breadth First Search, BFS）這兩種。DFS 相對簡單一點那就從 DFS 開始入門吧。

GIF

說到這個搜索演算法就要講到圖的問題，有學過離散數學或者數據結構的都知道，圖是一個點集合加上一個邊的集合一個邊對應兩個定點，屬於一種二元關係。

如果你沒學過的話上面那句話省略，直接看這裡：舉個例子講，微信朋友圈可以看成一個很大的圖，每個人都是一個頂點，彼此是好友彼此的朋友圈就能看到，相當於彼此的可達的。這個問題一抽象化就能算出只要你的朋友圈連接著多少人了。假如你發張你的自拍，你的每個好友都轉發，你好友的好友也都轉發.....然後全世界都知道你長什麼樣子了。所以小編的文章能怎麼樣還是需要你們這些第一批種子用戶的。

直接形象化的上圖

了解什麼是圖了，那麼我們從圖的遍歷開始講，給定一個包含N個頂點的圖，以及圖上的M條邊。讓你遍歷圖中的每一個頂點恰好一次。圖的遍歷有很多用途，比如判斷一個圖是不是連通的。和判斷你的微信能不能連接全世界是一樣的。

我們說說到一個演算法首先考慮的是他的實現，要實現的話就得要存儲，看問題我們是有兩個集合（點集和邊集）集合一般的思想就是通過一個數組集合來存儲，通過對點集的標號，找到與數組下標的關係，我們就能實現存儲。

其實我們有兩種方法來存儲邊集。一種叫做鄰接矩陣表示法，另一種叫鄰接表表示法。

鄰接矩陣是說我們用一個二維矩陣A來表示邊集。Aij=0表示頂點i和頂點j之間不存在邊，Aij=1表示頂點i和頂點j之間存在邊。如果我們用鄰接矩陣表示上圖，是這個樣子：

在程序中，我們一般用一個二維數組來表示鄰接矩陣: int a[N+1][N+1]。a[i][j]==1表示i和j之間有邊相連，a[i][j]==0表示i和j之間沒有邊相連。

鄰接表是圖中的每一個頂點i都有一個線性表，保存與i相連的頂點編號。

如果我們用鄰接矩陣表示上圖，是這個樣子：

在程序中，我們一般用一個數組嵌套vector的方法來表示鄰接表：vector g[N+1]，裡面保存著每一個與i相鄰的頂點編號。

上面講了什麼是搜索，如何存儲一個圖。那麼重頭戲來了我們不妨設從1號頂點起始。在搜索過程中，我們維護一個布爾數組bool visited[N+1]，這個數組用來表示每個頂點是不是已經遍歷過了。visited[i]==true表示頂點i已經遍歷過了，visited[i]==false表示i還沒有遍歷過。DFS一般我們可以用遞歸實現，如果採用鄰接矩陣，偽代碼如下：