兩個圖形節點之間的固定長度路徑

如果給定圖形上的兩個節點，是否有一種算法在它們之間找到需要指定跳數的路由？任何節點都可以連接到任何其他節點。兩個圖形節點之間的固定長度路徑

當前的點位於二維空間，所以我不確定一個圖是否是最好的方法。

來源

2009-10-21 dig412

寫我不知道，如果一個很好的算法存在，但我不知道你是不是總是將有一個有效的解決方案。例如，如果您有三角形圖形，則不會從A點到B點找到需要3跳的路徑。 – 2009-10-21 20:22:52

如果您可以重新訪問節點，例如在圈子中旅行。從1到2，進入1-3-1-2。 3跳，你在那裏。 – DVK 2009-10-21 21:00:23

如果你有節點正在尋找以跳躍方式尋找路由，那麼一個圖可能是正確的方法。不過，我不確定我是否理解你想要做什麼以及約束是什麼，特別是關於「任何節點都可以連接到任何其他節點」......這似乎有點開放。

不管怎樣，與一些圖表示：

它似乎是從第一個節點開始，並從那裏進行深度優先搜索，並在以下情況下終止搜索：（a）所採用的跳數大於您指定的數字或（b）我們有到達第二個節點;這將確定連接兩個節點的第一條（不僅僅是）路徑（最多）多跳。

如果它必須完全是指定的跳數，如果跳數已經超過，則終止搜索的任何分支，如果您也到達了第二個節點，則終止成功。

來源

2009-10-21 20:30:58 Mikeb

你試過iterated-deepening DFS？

來源

2009-10-21 20:41:26 dirkgently

啞方法:(數據結構是堆棧數組）。這基本上是廣度優先搜索（BFS）深度N，除了如果允許循環（你沒有澄清，但我假設他們是），你不排除訪問節點進一步搜索。索引0（索引=深度）

對於每個電平/指數存儲在陣列中的堆疊上

推起始節點「升」 0-N：

有關各節點一個存儲在級別「l」的堆棧，找到它的所有鄰居，並將它們推入存儲在級別「l + 1」中的堆棧。

重要事項：如果您的任務允許查找包含循環的路徑，請不要檢查您是否已經訪問過您添加的任何節點。如果不允許循環中，使用訪問節點的哈希值，當你結束等級「N-1」不添加任何節點兩次**
停止。
將您剛剛添加到堆棧的所有節點循環到索引「N」並找到您的目標節點。如果找到了：成功，如果沒有，就沒有這樣的路徑。

請注意，如果「每一個節點可以連接」你在暗示一個完全連通圖，則存在不涉及實際訪問節點

數學答案（不過，公式爲過長的StackOverflow的文本輸入字段）

來源

2009-10-21 20:49:06 DVK

只是在開玩笑 - 如果完全連通的圖N> = 3的節點的數目可能在任何步驟S中從任何節點行進到任何節點。如果S％3 == 0，則繞過用於S/3-1次，然後轉到任何其他節點，返回到目的地，然後轉到目標節點。如果S％3 == 1，則圍繞任何三角形行駛S/3-1次，然後前往目標節點。如果S％3 == 2，則繞S/3-1周的任何三角形行進，然後轉到任何其他節點，然後轉到目標節點。 DONE。 – DVK 2009-10-21 20:59:34

兩個圖形節點之間的固定長度路徑

回答

相關問題