DFS for Graph，標記爲已訪問

Question

我正在爲（鏈接列表）圖實現DFS。

我的圖形結構如：http://i.imgur.com/Pm9jC.png

正如你可以看到，有一個名爲「A」的許多節點。就頂點而言它們是相同的，但它們在節點方面實際上是不同的。實施DFS涉及在某個時刻將「a」標記爲已訪問。這看起來很簡單，但我希望你能在這裏看到我的問題。有很多「a」標記爲已訪問。我希望我在這裏做錯了什麼。

問題： - 首先標記「a」爲已訪問並將其推入堆棧s。這有效地將第一個鄰接鏈表中的節點「a」標記爲已訪問，但其他鄰接鏈表中的所有其他節點「a」仍然標記爲「未訪問」。 - 然後考慮「b」，因爲它是第一個未訪問的相鄰頂點「a」。將其標記爲已訪問並將其推入堆棧。 - 現在我們正在探索「b」。從第二個鄰接鏈表中，與「b」相鄰的頂點是「a」，並且這一個是未訪問的，所以我們再次將它推入堆棧。錯誤！

當然，我可以編寫一個markVisit（$ vertex）方法，將所有出現的「a」標記爲一次訪問，但我認爲我在上面的實現中沒有正確的方法。謝謝你的幫助。

Answer 1

markVisit($vertex)應該是正確的，您需要記住您已經訪問過哪些頂點。 DFS關注頂點，而不是邊緣。