Java深度優先遞歸函數

Question

在Java中編寫遞歸函數（圖論），從一個隨機的起點開始，獲取4x4表中的所有路徑。可能的方向是水平的，垂直的&對角線，但我有一個要求，不能訪問兩次相同的位置。

到目前爲止，該腳本工作正常，我得到了很多組合。問題是，在函數的for循環中，當有多種可能的方式時，在第二個循環和下一個循環中我得到了錯誤的結果，因爲布爾型[]臨時值沒有回到他以前的值。

我希望有人能夠理解我的英語和我的問題。這是我到目前爲止的代碼：

// here I define a constant input of values: 
String letters = "1548987425461854" 

// This matrix shows all possible directions from every startpoint in the matrix: 
// from the second value, you may get to the following locations: 1,3,5,6 and 7 
    private int[][] matrix = { 
     {1,4,5}, 
     {0,2,4,5,6}, 
     {1,3,5,6,7}, 
     {2,6,7}, 
     {0,1,5,8,9}, 
     {0,1,2,4,6,8,9,10}, 
     {1,2,3,5,7,9,10,11}, 
     {2,3,6,10,11}, 
     {4,5,9,12,13}, 
     {4,5,6,8,10,12,13,14}, 
     {5,6,7,9,11,13,14,15}, 
     {6,7,10,14,15}, 
     {8,9,13}, 
     {8,9,10,12,14}, 
     {9,10,11,13,15}, 
     {10,11,14} 
}; 

// Here begins the recursive function 
public List<Combination> depthFirst(int vertex, boolean[] visited, Combination zeichen, List<Combination> combis){ 
    // A temporary list of booleans to mark every value position visited or not 
    boolean[] tempvisited = new boolean[16]; 

    // combis is the whole list of ways, zeichen is just the actual combination 
    zeichen.name = zeichen.name + this.letters.charAt(vertex); 
    combis.add(zeichen.name); 

    //marks actual value as visited 
    visited[vertex] = true; 
    for(int i = 0; i < 16; i++){ 
     tempvisited[i] = visited[i]; 
    }//end for 

    // going to next possible locations 
    for (int i = 0; i < this.matrix[vertex].length; i++) { 
     if (!visited[this.matrix[vertex][i]]) {   
      combis = depthFirst(this.matrix[vertex][i], tempvisited, zeichen, combis);  
     }//end if 
    }//end for 
    return combis; 
} 

Answer 1

你有正確的想法與tempvisited，製作副本。但是你在錯誤的地方這樣做。

您正在設置visited[vertex] = true，這意味着您通過的visited正在改變。你想要的是visited永不改變。製作一份副本，並對該副本進行更改。

此外，我注意到你每次都使用相同的zeichen。所以，如果你有一個3步長的路徑，你的combis列表將是相同的zeichen的3個副本。這似乎不正確。

Answer 2

您在第一個for循環之前將visited [vertex]設置爲true;在您返回之前，您可以重置爲false。如果每個呼叫都撤銷它所做的更改（直接），那麼每次呼叫都將返回，並在呼叫完成時返回到其狀態。沒有臨時需要。

Answer 3

查看深度優先搜索（DFS）的其他遞歸解決方案（僞代碼）。

void search(Node root) { 
if (root == null) return; 

visit(root); 
root.visited = true; 
foreach (Node n in root.adjacent) { 
    if (n.visited == false) 
    search(n); 
} 
} 

Answer 4

其實你不需要一個訪問數組的副本。在depthFirst的reccurrent調用之前將該節點標記爲訪問，然後在調用之後立即「取消標記」。就像：

for (int i = 0; i < this.matrix[vertex].length; i++) { 
    if (!visited[this.matrix[vertex][i]]) {  
     visited[this.matrix[vertex][i]] = true; 
     combis = depthFirst(this.matrix[vertex][i], tempvisited, zeichen, combis);  
     visited[this.matrix[vertex][i]] = false; 
    }//end if 
}//end for