使用DFS遍歷MST，在一個頂點開始和結束？

Question

我正在嘗試遍歷MST。我希望能夠從一個頂點開始和結束並訪問每個頂點（TSP）。我不關心效率，我只想訪問MST中的每個頂點並返回到源頂點。有什麼建議麼？我試過實施MST

ArrayList<ArrayList<Vertex>> mst = new ArrayList<ArrayList<Vertex>>(); 

但我不知道如何開始做DFS。

Answer 1

不要對最小生成樹進行深度優先遍歷，先做遍歷。在前序遍歷中，樹的根是第一個遍歷的節點，所以在MST的前序遍歷之後，將根添加到遍歷的節點。這會給你樹中所有以root開頭和結尾的節點。這會讓你開始和結束MST的根。