使用深度優先搜索適當遍歷無向圖？

Question

我有一個無向圖，我需要使用深度優先搜索來遍歷。

下面的excel圖表顯示每個節點在標記列中遍歷後被標記，edgeTo列顯示哪個節點將我們帶到該節點。例如，我們從節點5到節點1，從節點7到節點2，等等。

我的問題是針對節點6和8，因爲它們與主圖分開，我該如何正確遍歷它？我的猜測是，我從6開始到8，但是因爲6已經被訪問過，所以我不會從8返回到6.因此，第6行在edgeTo列中留空。

我正確嗎？我的圖表是否正確？

Answer 1

深度優先搜索基本上是用來發現在圖中，兩個節點之間的路徑。您示例的圖形是斷開連接，即圖中存在兩個節點，因此圖中沒有路徑將這些節點作爲端點。

6,8顯然屬於不同的子圖，因此，你無法找到0-8和DFS之間的路徑將返回IMPOSSIBLE或沒有路徑中找到節點。除此之外，你的圖表是正確的。