在無向圖中找到所有唯一路徑

我遇到了一個問題，我需要在< = 4的無向圖中搜索全部唯一路徑。該圖基本上是一個網格，並且所有連接僅在直接鄰居之間（4路）。在無向圖中找到所有唯一路徑

一條路徑不能多次訪問同一個頂點。
一條路徑可以訪問任何頂點的數量來創建路徑。
路徑包含至少2個頂點。

我該如何解決這個問題？

enter image description here

來源

2011-04-04 Morrowless

這是一個連接圖嗎？ – Argote 2011-04-04 08:34:57

我無法理解獨特路徑的含義，購買你的定義我認爲最多有4 * n條獨特路徑，每條路徑都是一條邊。 – 2011-04-04 08:41:00

我相信圖形已連接（所有頂點都可以到達） – Morrowless 2011-04-04 08:42:51

這是我剛剛想出了僞代碼：

開始在任一節點。
獲取它的所有路徑
看他們領先的地方，如果它是一個沒有被訪問過的節點，那麼訪問它。
從前面的路徑節點遞歸地調用相同的函數。
保留路徑數的計數器。

這將是這個代碼在Java中（未經測試）：

public int getPaths (Node n, Set<Node> nodesVisited) { 
    int pathCount = 0; 
    for (Path p : n.getPaths()) { 
     Node otherSide = p.getOtherNode(n); // Where this function basically takes a node and gets the other node in the path 
     if (!(nodesVisited.contains(otherSide))) { 
      nodesVisited.add(otherSide); 
      pathCount += 1 + getPaths(otherSide, new Set<Nodes>(nodesVisited)); 
     } 
    } 
    return pathCount; 
}

這應該發現從一個起點節點的路徑。你可以在每個節點上啓動它，但你會得到一些重複。爲了除掉它們，你還需要返回路徑。

來源

2011-04-04 08:37:01 Argote

謝謝，這聽起來像它可以工作。我今晚會嘗試。 – Morrowless 2011-04-04 09:18:39

已確認可以正常工作，儘管我需要設法加快這一點。 – Morrowless 2011-04-04 14:16:59

在無向圖中找到所有唯一路徑

回答

相關問題