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

最近在寫分支定界求TSP的一個(gè)小項(xiàng)目，涉及到圖和樹的各種知識(shí)，就淺淺的從無向圖的遍歷開始總結(jié)一下近期的學(xué)習(xí)工作，使用DFS的遞歸遍歷無向圖。

鄰接矩陣、鄰接表等都可以用來表示一張圖，這里使用鄰接表數(shù)組來表示，即以頂點(diǎn)為索引的列表數(shù)組，具體實(shí)現(xiàn)使用字典來創(chuàng)建鄰接表數(shù)組。

深度優(yōu)先搜索DFS簡(jiǎn)單地來說，就是在訪問其中一個(gè)頂點(diǎn)時(shí)，將它標(biāo)記為已訪問，遞歸的訪問它所有沒有被標(biāo)記的相鄰頂點(diǎn)。

老習(xí)慣，上代碼。

運(yùn)行看結(jié)果。

淺淺的分析一下遞歸的過程

dfs(0) ---dfs(1)---0已經(jīng)被標(biāo)記了，下一個(gè)dfs(3)---1已經(jīng)被標(biāo)記了，所以下一個(gè)dfs(2)---graph[2]里的0,3都被標(biāo)記了，回到graph[3],接著dfs(5)--3已經(jīng)被標(biāo)記了，所以dfs(6）---接下來就簡(jiǎn)單了，dfs(4）。好像就結(jié)束了應(yīng)該是這樣吧。

到這里如果就結(jié)束的話，顯得敷衍，折騰了一下，實(shí)現(xiàn)了一個(gè)簡(jiǎn)單有點(diǎn)笨的s-v的路徑構(gòu)建的功能，還是用上面的例子來說明，最后visited = [0,1,3,2,5,6,4]，根據(jù)這個(gè)標(biāo)記順序，會(huì)有且僅有0-1，1-3，3-2，3-5，5-6，6-4被選中（別問為什么，這是我的規(guī)則）。

首先運(yùn)行前面的dfs,得到 visited = [0,1,3,2,5,6,4]，根據(jù)這個(gè)標(biāo)記順序，會(huì)有且僅有0-1，1-3，3-2，3-5，5-6，6-4被選中（別問為什么，這是我的規(guī)則）。看第4和5行，將構(gòu)建u-v的路徑轉(zhuǎn)為構(gòu)建v-u的路徑。

會(huì)有人好奇為啥0到5的路徑為啥不是0-3-5這條，因?yàn)?-3沒有被標(biāo)記啊！至于為什么，這就是我的規(guī)則，別管（懂的自然會(huì)懂我的心路歷程，不懂就算，反正構(gòu)建路徑又不對(duì)成本、距離等做要求)。




審核編輯：劉清