在無向圖中查找第n級路徑？

我已創建了6個頂點，在視覺上表示這樣的無向圖：http://i.imgur.com/EtQyspG.png 在無向圖中查找第n級路徑？

我想編寫一個腳本，可以找到從起點的所有路徑，而不重新訪問在同一個節點，沒有給定終點。

的BFS，DFS，A *算法我看過的每個實例都需要一個最終目的節點。然而，在更大的曲線圖可以是NP-很難找到從點A的所有可能的途徑爲指向Z.爲此，我想找到該是移動一組數範圍內實現的所有目的地的所有路徑（在此曲線圖例如 - 3個移動== 4最大頂點路徑）

我編碼使用PHP陣列與每個鍵是一個頂點和包含在相鄰的點其陣列的圖形：

<?php 

$graph[1] = array(2,6); 
$graph[2] = array(1,4); 
$graph[3] = array(4,5); 
$graph[4] = array(2,3,6); 
$graph[5] = array(6,3); 
$graph[6] = array(1,5,4);

我不知道一個算法，但是這樣執行路徑搜索。我需要的輸出會是這樣的：

Path 1: 1,2 
Path 2: 1,2,4 
Path 3: 1,2,4,3 
Path 4: 1,6 
Path 5: 1,6,4,3 
Path 6: 1,6,5 
Path 7: 1,6,5,3

我沒有問題，編寫所需的代碼，但對於算法/功能（假設樹遍歷的遞歸？）必要的步驟是很難理解的。

問題：什麼方法/算法應使用要做到這一點，和你有一個例子（或至少僞代碼），顯示運行方式給出的圖形輸入數組？

來源

2013-02-24 server_kitten

那麼，在一個密集圖（| E |〜O（| V |^2））中，輸出的大小是最大移動量的指數，任何程序都會時間至少與要輸出的數據的大小成線性關係。

做你問什麼最簡單的方法是採取香草遞歸DFS算法，並對其進行修改，使

1）頂點的堆保持在一個實際的堆棧（我的意思是陣列/矢量/ Python列表/等你有什麼等價的PHP）。在調用之前將目標頂點插入它，在調用返回後將其彈出。

2）到達深度爲k時，功能打印堆棧輸出，並返回

3）遞歸函數「取消標記」當前頂點剛剛返回

之前，我不能幫你用PHP特別雖然。

來源

2013-02-24 22:07:27 yonil

單的出發點和分支告訴你建立一個樹。這只是深度有限的樹搜索。在每個級別，您需要修剪已經訪問過的節點。僞代碼在wiki文章中

來源

2013-02-24 22:01:00 stark

在無向圖中查找第n級路徑？

回答

相關問題