Java的遞歸找到一個圖形

我正在寫一個小程序，着眼於圖形，並期待從任何兩個給定點的所有路徑。

點是ABCDE並且在曲線圖上的連接如下...

A->B, A->D, A->E 

B->C 

C->D, C->E 

D->C, D->E 

E->B

我需要編碼它，以便它看起來在其是小於一定長度的所有可能的路徑（比方說30）。規範的古怪的一點是，它可以訪問目的地路徑的一部分，例如：

啓動位於C將C可遵循：

CDC，CEBC，CEBCDC，CDCEBC，CDEBC，CEBCEBC， CEBCEBCEBC

現在我的代碼如下......

private void findAllPaths(LinkedList path, Junction node, Junction end) 
{ 
    path.add(node); 
    if(node == end && path.size() > 1) 
    { 
     System.out.println(path); 
    } 
    else 
    { 
     for(Road r : node.getAdjacencies()) 
     { 
      if(path.size() < 30) findAllPaths(path, r.getTarget(), end); 
     } 
    } 
}

這使我的路徑：C，d，C] [C，d，C，E，B，C] [C ，D，C，E，B，C，E，B，C]

我的問題是，遞歸似乎不像我期望的那樣發生。它只會跟隨每個節點的第一個相鄰節點，並且從不回退嘗試其他節點。

如果任何人都可以看到我的問題出在哪裏，或看到我的問題，請發帖！所有幫助將不勝感激...

乾杯，

Djoodle

來源

2012-02-28 DJOodle

我不會用循環遞歸。我個人會走在一條路上，回頭一步，而不是試圖獲得單個節點的所有路徑。 – m0skit0 2012-02-28 13:33:38

研究實現[Dijkstra算法]（http://en.wikipedia.org/wiki/Dijkstra's_algorithm），然後使用兩個起始節點中的每一個運行一次。這可能比你想要做的更簡單。 – 2012-02-28 13:35:14

你不刪除節點，你已經嘗試過之後，再次：

private void findAllPaths(LinkedList path, Junction node, Junction end) 
{ 
    path.add(node); 
    // etc... 
    path.removeLast(); 
}

來源

2012-02-28 13:32:45

哈哈！我知道這是一件愚蠢的事... Thankyou我的朋友，很贊！ – DJOodle 2012-02-28 13:49:10

@DJOodle考慮接受這個答案，如果它解決了你的問題。 – Hedja 2012-02-28 13:54:48

Java的遞歸找到一個圖形

回答

相關問題