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

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

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

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

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

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

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

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

到這里如果就結(jié)束的話，顯得敷衍，折騰了一下，實(shí)現(xiàn)了一個簡單有點(diǎn)笨的s-v的路徑構(gòu)建的功能，還是用上面的例子來說明，最后visited = [0,1,3,2,5,6,4]，根據(jù)這個標(biāo)記順序，會有且僅有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ù)這個標(biāo)記順序，會有且僅有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的路徑。

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




審核編輯：劉清