何為深度優(yōu)先遍歷0.o呢？DFS是圖論中的經(jīng)典算法。其利用深度優(yōu)先搜索算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮?#xff0c;利用拓?fù)渑判虮砜梢苑奖愕慕鉀Q很多相關(guān)的圖論問題，如最大路徑問題等等。

基本思想：（一條路走到底然后再一個腳步一個腳步返回~）

首先以一個未被訪問過的頂點作為起始頂點，沿當(dāng)前頂點的邊一直走下去，走到未訪問過的頂點；

當(dāng)沒有未訪問過的頂點時，則回到上一個頂點，繼續(xù)試探別的頂點，直到所有的頂點都被訪問過。

以這個圖為例：以a頂點作為起始點，則其深度遍歷為：a,c,h,k,f,e,d

簡單說明一下：首先從a開始，一條路走到底a,c,h,k,f

走到f時發(fā)現(xiàn)fd下一個節(jié)點h或者a都被訪問過了，所以f返回上一個節(jié)點，即k

k的下一個節(jié)點e還沒被訪問，所以訪問他，以此類推則可以得到如下：a,c,h,k,f,e,d

了解了DFS的遍歷過程，那如何用程序來實現(xiàn)這個過程呢？

下面將給大家介紹：

首先，先去準(zhǔn)備一個堆棧，一個Set（是的，還是用來注冊用的，BFS遍歷的時候也是不能重復(fù)的）

下面給上流程圖：

1.首先，先把node節(jié)點放進(jìn)去set和stack堆棧中（有沒有發(fā)現(xiàn)一個很有趣的事情，set和stack總是同時add，同時，也打印出來）

2.?遍歷棧頂?shù)膎ext節(jié)點，如果set中沒包含這個節(jié)點，就把這個節(jié)點和前一個節(jié)點一起添加到stack中去，

?同時把該節(jié)點也添加到set中，同時打印，最后break。當(dāng)set中已經(jīng)包含了該節(jié)點的時候，就不執(zhí)行下面了。

（大家對照著程序一起看，相信是可以看懂滴，加油0。0）

（看得懂覺得不錯的幫忙點個贊呀~）

總結(jié)

以上是生活随笔為你收集整理的图 之遍历----深度优先遍历0.o的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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