我遇到了一個問題,我需要在< = 4的無向圖中搜索全部唯一路徑。該圖基本上是一個網格,並且所有連接僅在直接鄰居之間(4路)。在無向圖中找到所有唯一路徑
- 一條路徑不能多次訪問同一個頂點 。
- 一條路徑可以訪問任何 頂點的數量來創建路徑。
- 路徑包含至少2個頂點。
我該如何解決這個問題?
我遇到了一個問題,我需要在< = 4的無向圖中搜索全部唯一路徑。該圖基本上是一個網格,並且所有連接僅在直接鄰居之間(4路)。在無向圖中找到所有唯一路徑
我該如何解決這個問題?
這是我剛剛想出了僞代碼:
這將是這個代碼在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;
}
這應該發現從一個起點節點的路徑。你可以在每個節點上啓動它,但你會得到一些重複。爲了除掉它們,你還需要返回路徑。
謝謝,這聽起來像它可以工作。我今晚會嘗試。 – Morrowless 2011-04-04 09:18:39
已確認可以正常工作,儘管我需要設法加快這一點。 – Morrowless 2011-04-04 14:16:59
這是一個連接圖嗎? – Argote 2011-04-04 08:34:57
我無法理解獨特路徑的含義,購買你的定義我認爲最多有4 * n條獨特路徑,每條路徑都是一條邊。 – 2011-04-04 08:41:00
我相信圖形已連接(所有頂點都可以到達) – Morrowless 2011-04-04 08:42:51