從起點開始的深度優先算法

Question

好吧，我在網上瀏覽過很多東西，它只是沒有真正點擊我。

我有一個ArrayList towns = new ArrayList<Town>與我將執行DFS的城鎮。

我填補這個陣列用〜8個鎮

我有一個整數int i（在ArrayList中的鎮指數其中具有是第一路徑）

我有一個初始距離double dist = 0

我有一個功能distBetween(Town a, Town b)這就是它所說的。

我有一個Arraylist route = new ArrayList<Town>()其中包含城鎮的順序，這取決於我正在採取的路徑。

現在我有執行深度優先搜索的主要功能（根據在線研究遞歸）。

public static void dfs(){ 

    // what goes here 

} 

我需要的城鎮添加到路由陣列，並根據深度優先搜索算法中刪除。我還需要編輯dist變量。

我會如何解決這個問題。有人可能會提供一些僞代碼或評論，只是解釋做什麼。我似乎無法應用我在網上找到的其他算法。如果我能得到一個特定於我的情況的解釋，那將是很棒的。

我可以從town刪除索引i如果它使得它更容易執行搜索。

Answer 1

我會假設你有一個State類具有以下屬性（如果你喜歡的圖形，使用Node代替State）：

Set<Town> unused;  // towns not yet visited 
ArrayList<Town> path; // current path 
double dist;    // total distance in path 

然後使用代碼像這樣的遞歸嘗試每一個可能的使用DFS的路徑。在第一次調用，使用dfs(emptyState, startTown, null)：

public static void dfs(State s, Town last, State best) { 
    s.path.add(last); 
    s.unused.remove(last); 
    if (unused.empty()) { 
     // all towns visited - distance and path are now complete 
     if (best == null || s.dist < best.dist) best = s; 
     return; 
    } 
    for (Town t : s.unused) { 
     State next = s.copy(); // a copy of State s 
     next.dist += distBetween(last, t); 
     dfs(next, t); 
    } 
} 

調用該函數後，所有的路徑都已經訪問過一次（在DFS順序），best將包含最短的一個。請注意，對於許多城市來說，這變得非常緩慢 - O（n！）。

Answer 2

DFS算法

1. 輸入頂點和圖G =（V，E）的邊緣。
2. 輸入源頂點並將其分配給變量S.
3. 將源頂點推入堆棧。
4. 重複步驟5和6，直到堆棧爲空。
5. 彈出堆棧的頂層元素並顯示它。
6. 推送剛剛彈出的元素的鄰居頂點，如果它不在隊列中並顯示（即;未訪問）。
7. 退出。

要存儲頂點和邊緣，您將需要一個adjacency matrix。