騎士旅行用Java（遞歸），使用圖形和DFS

Question

我試圖來計算一個5x5的領域的所有可能的騎士招式：

要做到這一點，我試圖使用DFS（深度優先搜索）類和Graph類。

我想這可能是太多的代碼（也許沒有足夠的相關），在這個崗位粘貼這些整個類，所以我在這裏顯示出來：

Graph.java

DepthFirstSearch.java

圖。 Java使用Bag.java：

​​

外地也看起來像這樣（用一個id爲每個字段）：

0 1 2 3 4 
5 6 7 8 9 
10 11 12 13 14 
15 16 17 18 19 
20 21 22 23 24 

以下屬性在CalculatePath方法使用，這應該算可以遊覽的騎士可能需要從特定廣場參觀每平方米的量正好一次（應該花一兩分鐘的時間來解決它）。

可能騎士的步驟定義（主類）就像這樣（用圖，G的邊緣）：

G.addEdge(0, 11); 
G.addEdge(0, 7); 

G.addEdge(1, 8); 
G.addEdge(1, 10); 
G.addEdge(1, 12); 

G.addEdge(2, 5); 
G.addEdge(2, 9); 
G.addEdge(2, 11); 
G.addEdge(2, 13); 

G.addEdge(3, 6); 
G.addEdge(3, 12); 
G.addEdge(3, 14); 

G.addEdge(4, 7); 
G.addEdge(4, 13); 

G.addEdge(5, 2); 
G.addEdge(5, 12); 
G.addEdge(5, 16); 

G.addEdge(6, 15); 
G.addEdge(6, 17); 
G.addEdge(6, 3); 
G.addEdge(6, 13); 

G.addEdge(7, 0); 
G.addEdge(7, 4); 
G.addEdge(7, 10); 
G.addEdge(7, 14); 
G.addEdge(7, 16); 
G.addEdge(7, 18); 

G.addEdge(8, 1); 
G.addEdge(8, 17); 
G.addEdge(8, 19); 
G.addEdge(8, 11); 

G.addEdge(9, 2); 
G.addEdge(9, 12); 
G.addEdge(9, 18); 

G.addEdge(10, 1); 
G.addEdge(10, 21); 
G.addEdge(10, 7); 
G.addEdge(10, 17); 

G.addEdge(11, 0); 
G.addEdge(11, 2); 
G.addEdge(11, 20); 
G.addEdge(11, 22); 
G.addEdge(11, 8); 
G.addEdge(11, 18); 

G.addEdge(12, 1); 
G.addEdge(12, 3); 
G.addEdge(12, 21); 
G.addEdge(12, 23); 
G.addEdge(12, 5); 
G.addEdge(12, 9); 
G.addEdge(12, 15); 
G.addEdge(12, 19); 

G.addEdge(13, 2); 
G.addEdge(13, 4); 
G.addEdge(13, 22); 
G.addEdge(13, 24); 
G.addEdge(13, 6); 
G.addEdge(13, 16); 

G.addEdge(14, 3); 
G.addEdge(14, 23); 
G.addEdge(14, 7); 
G.addEdge(14, 17); 

G.addEdge(15, 6); 
G.addEdge(15, 12); 
G.addEdge(15, 22); 

G.addEdge(16, 5); 
G.addEdge(16, 7); 
G.addEdge(16, 13); 
G.addEdge(16, 23); 

G.addEdge(17, 6); 
G.addEdge(17, 8); 
G.addEdge(17, 10); 
G.addEdge(17, 14); 
G.addEdge(17, 20); 
G.addEdge(17, 24); 

G.addEdge(18, 7); 
G.addEdge(18, 9); 
G.addEdge(18, 11); 
G.addEdge(18, 21); 

G.addEdge(19, 8); 
G.addEdge(19, 12); 
G.addEdge(19, 22); 

G.addEdge(20, 11); 
G.addEdge(20, 17); 

G.addEdge(21, 10); 
G.addEdge(21, 12); 
G.addEdge(21, 18); 

G.addEdge(22, 11); 
G.addEdge(22, 13); 
G.addEdge(22, 15); 
G.addEdge(22, 19); 

G.addEdge(23, 12); 
G.addEdge(23, 14); 
G.addEdge(23, 16); 

G.addEdge(24, 13); 
G.addEdge(24, 17); 

int currentSquare = 20; 
calculatePath(currentSquare); 
System.out.println("From square " + currentSquare + " there are " + tours + " possible tours."); 

這裏就是我試圖找到可能的旅行團：

private static void calculatePath(int currentSquare) { 
     boolean foundChoice = false; 
     for (int point : G.adj(currentSquare)) { 

      if (dfs.marked(currentSquare)) { 
       foundChoice = true; 
//    dfs.unmark(currentSquare); 
       calculatePath(point); 
      } 
     } 
     if (!foundChoice) { 
      tours++; 
      dfs.unmark(currentSquare); 
     } 
     System.out.println(currentSquare + " - tours: " + tours); 
    } 

例如，如果我嘗試通過calculatePath(20)調用此遞歸函數，它應該使用該字段上的每個方塊返回該方塊的所有可能的遊覽（tours）。

未標記的正方形是已經到達的正方形，在同一遊覽中不應再可見。

現在，問題是我不能讓CalculatePath跳過已經訪問過的方塊（輸出顯示它從20到17，從20到11，然後停止遞歸方法）。

另外，該方法還沒有計算多次巡視。我想首先正確計算一條路徑，並最終計算出所有可能的巡視路線。

我正在使用的所有代碼都在這篇文章中提到 - 包括上面鏈接中的類。

Answer 1

還有仍然:)這個代碼的一些問題，但它看起來像你正在取得進展。

您的方法DepthFirstSearch.marked對我來說似乎不對。如果成功將標記從false更改爲true，我會認爲它應該返回true。這裏您只返回marked[w]的值。

您的DepthFirstSearch構造函數似乎試圖標記所有相鄰（及其所有相鄰點）。這看起來很奇怪 - 你如何期待這個工作？用於避免循環的常規DFS機制是在遞歸完成時遞歸併重新標記標記時，在您觸摸的每個位置留下標記。在這裏，您似乎在開始時標記了所有方塊，然後在完成一輪所有相鄰方的未標記標記時將其取消標記。