一、圖的遍歷概念

圖的遍歷指從圖中某一頂點出發(fā)（任意一個頂點都可以作為訪問的起始頂點），按照某種遍歷方法，對圖中所有的頂點訪問一次且只訪問一次。圖與樹不一樣，其中一個頂點可能與多個頂點相連，所以需記錄已訪問過的頂點，當訪問一個頂點后，考慮如何選取下一個要訪問的頂點。

• 圖的遍歷分為兩種，深度優(yōu)先搜索和廣度優(yōu)先搜索，這兩種方法對無向圖和有向圖都適用。

二、深度優(yōu)先搜索（DFS）

（一）DFS算法步驟

前面文章中，講到過二叉樹的先序遍歷，其實這里圖的深度優(yōu)先搜索（DFS）是由其推廣而來的。

二叉樹的先序遍歷中，首先是根結點，遍歷完根結點的左子樹，然后再遍歷完根結點的右子樹，依次下去至所有結點都遍歷到。

圖的深度優(yōu)先遍歷（DFS）需要借助棧來遍歷：
①首先，選取圖中某一頂點v_i作為起始點訪問；
②任意選取一個與v_i鄰接的頂點，且該頂點未被訪問，一直重復下去，直到圖中所有與v_i連通的頂點都被訪問到；【可概括為由起始頂點開始，沿著一條路徑盡可能地深入搜索該圖，直到無法再繼續(xù)下去】
③若還有頂點未被訪問到，則另外選取一個未被訪問的頂點再次作為起始點，回溯到上一個未訪問的頂點，重復以上步驟，直至圖中所有結點被訪問。

可以看出DFS算法是一個遞歸過程，其中需借助棧完成操作。

1、鄰接表DFS算法步驟

例如下面這個無向圖：

該圖的鄰接表如下：

通過鄰接表進行深度優(yōu)先搜索的步驟如下（以V1為訪問起始點，不唯一）：
1、首先訪問0，即V1，訪問后標記已訪問過；
2、查看V1單鏈表，第一個未訪問的鄰接頂點為2，即V3，并以V3為出發(fā)點繼續(xù)深度遍歷；
3、查看V3單鏈表，其第一個未訪問的鄰接頂點為6，即V7，再以V7為出發(fā)點繼續(xù)深度遍歷；
4、查看V7單鏈表，其鄰接頂點為2，即V3，它已經(jīng)被訪問過，于是回到V3單鏈表，搜索下一個未被訪問的鄰接頂點；
5、查看V3單鏈表，其下一個未訪問的鄰接頂點為5，即V6，以V6為出發(fā)點繼續(xù)深度遍歷；
6、查看V6單鏈表，其鄰接頂點為2，也是已經(jīng)被訪問過，于是回到V3單鏈表，搜索下一個未被訪問的鄰接頂點；
7、查看V3單鏈表，其鄰接頂點為0，即V1，一開始被訪問過，于是回到V1單鏈表，搜索下一個未被訪問的鄰接頂點；
8、查看V1單鏈表，其下一個未訪問的鄰接頂點為1，即V2，并以V2為出發(fā)點繼續(xù)深度遍歷；
9、查看V2單鏈表，其第一個未訪問的鄰接頂點為4，即V5，再以V5為出發(fā)點繼續(xù)深度遍歷；
10、查看V5單鏈表，其第一個未訪問的鄰接頂點為7，即V8，再以V8為出發(fā)點繼續(xù)深度遍歷；
11、查看V8單鏈表，其鄰接頂點為4，即V5，已經(jīng)被訪問過，于是回到V5單鏈表，搜索下一個未被訪問的鄰接頂點；
12、查看V5單鏈表，其下一個未被訪問的鄰接頂點為1，即V2，于是回到V2單鏈表，搜索下一個未被訪問的鄰接頂點；
13、查看V2單鏈表，其鄰接頂點為3，即V4，并以V4為出發(fā)點繼續(xù)深度遍歷；
14、查看V4單鏈表，其鄰接頂點為7，即V8，再以V8為出發(fā)點繼續(xù)深度遍歷；
15、查看V8單鏈表，其鄰接頂點為3，即V4，再以V4為出發(fā)點繼續(xù)深度遍歷；
16、查看V4單鏈表，其鄰接頂點為1，即V2，再以V2為出發(fā)點繼續(xù)深度遍歷；
17、查看V2單鏈表，其鄰接頂點為0，即V1，再以V1為出發(fā)點繼續(xù)深度遍歷；
18、查看V1單鏈表，其鄰接頂點為2，即V3，V3中已經(jīng)不存在未訪問的頂點，于是回到V1單鏈表。
19、查看V1單鏈表，下一個鄰接頂點為1，即V2，V2中已經(jīng)不存在未訪問的頂點，最后回到V1單鏈表，遍歷完成。
故該圖的深度優(yōu)先遍歷序列為：V1、V3、V7、V6、V2、V5、V8、V4。

2、鄰接矩陣DFS算法步驟
通過圖的鄰接矩陣實現(xiàn)深度優(yōu)先搜索，例如下面這個圖（以V1為訪問起始點，是唯一的）：

例如，對于下面這個有向圖，對其進行深度優(yōu)先搜索：

其鄰接矩陣如下：

1、由V1開始，如下表【第一行為回退點，第二行為深度優(yōu)先搜索得到的序列】：

2、通過其鄰接矩陣知，訪問第一行第二列的1對應的V2頂點，由于它是在V1的行中被訪問到的，所以回退點為V1：

3、由于訪問了V2，即開始訪問V2行，訪問第二行第三列的1對應的V4頂點，由于它是在V2的行中被訪問到的，所以回退點為V2：

4、由于訪問了V4，即開始訪問V4行，訪問第四行第五列的1對應的V5頂點，由于它是在V4的行中被訪問到的，所以回退點為V4：

5、由于訪問了V5，即開始訪問V5行，由于第五行都為0，回退到V4，由于V4行頂點都訪問完，回退到V2，由于V2行頂點都訪問完，回退到V1行，此時V1行還剩第一行第三列的1對應的V3頂點未訪問，訪問該頂點：

6、至此，訪問完了圖中的所有頂點，即深度優(yōu)先搜索序列為V1、V2、V4、V5、V3。

對于深度優(yōu)先搜索（DFS），由于基于鄰接表的遍歷得到的序列可能不是唯一的，即根據(jù)邊的輸入次序不同，從而得到的鄰接表不同，從而遍歷序列不一樣；而基于鄰接矩陣所得到的DFS遍歷序列是唯一的。

寫出下面這個圖的深度優(yōu)先遍歷序列：

其深度優(yōu)先遍歷序列為：0，4，6，9，8，7，5，3，2，1。

（二）DFS的空間復雜度和時間復雜度

對于一個圖G=（V，E），由頂點集V和邊集E組成。
1、DFS算法的空間復雜度
由于DFS算法是一個遞歸算法，即遞歸頂點集V，通過DFS遍歷的空間復雜度為O(|V|)。

2、DFS算法的時間復雜度
時間復雜度取決于圖的存儲結構，若通過鄰接矩陣表示圖，則查找頂點的鄰接頂點所需時間為O(|V|)，總時間復雜度為O(|V²|)（鄰接矩陣為方陣n×n）；若通過鄰接表表示圖，則查找所有頂點的鄰接頂點所需時間為O(|E|)，訪問頂點所需時間為O(|V|)，即總時間復雜度為O(|V|+|E|)。

三、深度優(yōu)先生成樹（森林）

對一個連通圖或非連通圖進行DFS遍歷后，若將在遍歷過程中所經(jīng)歷過的頂點保留，則可以形成一棵樹或森林，即深度優(yōu)先生成樹或深度優(yōu)先生成森林；另外，基于鄰接表存儲的深度優(yōu)先生成樹或深度優(yōu)先生成森林也是不唯一的；而對于鄰接矩陣則是唯一的。

例如，上面這個無向連通圖遍歷DFS遍歷生成的深度優(yōu)先生成樹如下（基于鄰接表）：

例如，對于上面這個有向圖進行DFS遍歷：

它并不是連通圖，得到的深度優(yōu)先生成森林如下：

四、廣度優(yōu)先搜索（BFS）

（一）BFS算法步驟

前面文章中，講到過二叉樹的層序遍歷，其實這里圖的廣度優(yōu)先搜索（BFS）是由其推廣而來的。

二叉樹的層序遍歷中，層次優(yōu)先，當對一層的結點都遍歷完后，遍歷下一層，按照次序對每個結點的左、右孩子進行遍歷。

圖的廣度優(yōu)先搜索（BFS）需要借助到隊列來遍歷：
①首先，選取圖中某一頂點v_i作為出發(fā)點，訪問后將其入隊并標記為已訪問（使用隊列用于避免重復訪問，存放已經(jīng)訪問過的各鄰接頂點）；
②依次訪問與v_i鄰接的頂點，即當隊列不為空時檢查出隊頂點的所有鄰接頂點，訪問未被訪問的鄰接頂點并將其入隊，重復該過程；【可概括為由起始頂點開始，按照廣度優(yōu)先的順序逐層遍歷與當前頂點相鄰的頂點將其訪問】
③當隊列為空時跳出循環(huán)，即所有已被訪問的頂點的鄰接頂點均被訪問到，則此時遍歷完成。

可以知道BFS算法并不是遞歸過程，且要用到隊列。

1、鄰接表BFS算法步驟
例如下面這個無向圖：

該圖的鄰接表如下：

通過鄰接表進行廣度優(yōu)先搜索的步驟如下（這里以V1為訪問起始點，不唯一）：
1、首先訪問0，即V1，訪問后標記已訪問過，使其入隊，然后刪除當前隊頭結點；【V1】
2、遍歷V1單鏈表，使其未訪問的鄰接頂點2、1入隊并標記；【V2、V3】
3、訪問隊頭結點1并刪除，然后遍歷1對應的V2單鏈表，使其未訪問的鄰接頂點4、3入隊并標記；【V3、V4、V5】
4、訪問隊頭結點2并刪除，然后遍歷2對應的V3單鏈表，使其未訪問的鄰接頂點6、5入隊并標記；【V4、V5、V6、V7】
5、訪問隊頭結點3并刪除，然后遍歷3對應的V4單鏈表，使其未訪問的鄰接頂點7入隊并標記；【V5、V6、V7、V8】
6、訪問隊頭結點4并刪除，然后遍歷4對應的V5單鏈表，該單鏈表中無未訪問的頂點；【V6、V7、V8】
7、訪問隊頭結點5并刪除，然后遍歷5對應的V6單鏈表，該單鏈表中無未訪問的頂點；【V7、V8】
8、訪問隊頭結點6并刪除，然后遍歷6對應的V7單鏈表，該單鏈表中無未訪問的頂點；【V8】
9、訪問隊頭結點7并刪除，然后遍歷7對應的V8單鏈表，該單鏈表中無未訪問的頂點，此時隊列為空，遍歷結束；【】
故該圖的深度優(yōu)先遍歷序列為：V1、V2、V3、V4、V5、V6、V7、V8。

2、鄰接矩陣BFS算法步驟
通過圖的鄰接矩陣實現(xiàn)廣度優(yōu)先搜索，例如下面這個圖（以V1為訪問起始點，是唯一的）：

例如，對于下面這個有向圖，對其進行廣度優(yōu)先搜索：

其鄰接矩陣如下：

1、由V1行開始，如下表：

2、可得與其匹配的有V2、V3，填到表中V1之后：

3、由V2行開始，其中V4未訪問，填到V3之后：

4、由V3行開始，都為0，繼續(xù)下一行。
5、由V4行開始，其中V5未訪問，填到V4之后：

6、至此，該圖的所有頂點都已訪問到，得到的序列便是廣度優(yōu)先搜索，即深度優(yōu)先搜索序列為V1、V2、V3、V4、V5。

同樣，對于廣度優(yōu)先搜索，由于基于鄰接表的遍歷得到的序列可能不是唯一的，即根據(jù)邊的輸入次序不同，從而得到的鄰接表不同，從而遍歷序列不一樣；而基于鄰接矩陣所得到的遍歷序列是唯一的，這兩點和深度優(yōu)先搜索遍歷是一樣的。

（二）BFS的空間復雜度和時間復雜度

對于一個圖G=（V，E），由頂點集V和邊集E組成。
1、BFS算法的空間復雜度
通過BFS遍歷的空間復雜度為O(|V|)。

2、BFS算法的時間復雜度
時間復雜度取決于圖的存儲結構，若通過鄰接矩陣表示圖，則查找頂點的鄰接頂點所需時間為O(|V|)，總時間復雜度為O(|V²|)（鄰接矩陣為方陣n×n），這和DFS算法的時間復雜度是一樣的；若通過鄰接表表示圖，則每個頂點都入隊一次，即所需時間為O(|V|)，搜索頂點的鄰接頂點所需時間為O(|E|)，其時間復雜度為O(|V|+|E|)。

五、廣度優(yōu)先生成樹（森林）

• 與DFS遍歷一樣， 對一個連通圖或非連通圖進行BFS遍歷后，若將在遍歷過程中所經(jīng)歷過的頂點保留，則可以形成一棵樹或森林，即廣度優(yōu)先生成樹或廣度優(yōu)先生成森林；另外，基于鄰接表存儲的廣度優(yōu)先生成樹或廣度優(yōu)先生成森林也是不唯一的；而對于鄰接矩陣則是唯一的。

例如，上面這個無向連通圖遍歷BFS遍歷生成的深度優(yōu)先生成樹如下（基于鄰接表）：

例如，對于上面這個有向圖進行BFS遍歷：

它并不是連通圖，得到的廣度優(yōu)先生成森林如下：

例如寫出下面這個圖的廣度優(yōu)先遍歷序列：

其廣度優(yōu)先遍歷序列為：0，4，3，2，1，6，5，9，8，7。

六、DFS和BFS的基本應用

以上兩種遍歷算法都可以用于判斷圖的連通性，圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷中，若在遍歷中，所有的頂點都被訪問到，則圖是連通的，否則，圖是不連通的。

另外，同時也可計算圖中的連通分量數(shù)目，當一個圖為連通圖時，經(jīng)過遍歷后會訪問到所有的頂點，其中訪問過的頂點不會再次訪問，從而可以得到圖中的連通分量數(shù)目。文章來源地址http://www.zghlxwxcb.cn/news/detail-445558.html

到了這里，關于數(shù)據(jù)結構學習筆記——圖的遍歷算法（深度優(yōu)先搜索和廣度優(yōu)先搜索）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！