查找無向圖路徑的算法

-3

在無向圖中查找路徑的簡單算法是什麼？查找無向圖路徑的算法

2012-02-27 IAQ

在過去的一兩天內，有一組與圖形相關的Scheme問題進入Stack Overflow。示例：http://stackoverflow.com/questions/9426788/depth-first-search-dfs-for-undirected-graphs。這是一個功課問題嗎？ – dyoo 2012-02-27 04:13:44

是的，但另一個不是我的帖子 – IAQ 2012-02-27 04:31:30

強烈建議：請參閱：http://www.htdp.org/2003-09-26/Book/curriculum-ZH-35.html#node_chap_28以及http ：//www.htdp.org/2003-09-26/Book/curriculum-ZH-38.html – dyoo 2012-02-27 04:44:18

此問題的答案依賴於您的圖形表示。典型的算法是Dijkstra算法（注意，這個算法會找到最短路徑，但是工作正常）。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

這是一個相當簡單的算法來實現，也可能是尋路算法的最直觀之中。

來源

2012-02-27 01:52:31

我必須寫的函數只是假設有或沒有路徑時返回true或false。此外，該圖被定義爲 is_path？ '（3（（1 2）（2 3））1 3）其中3是頂點數，（（1 2）（2 3））是邊。然而，頂點的數量是可選的。我看着Dijkstra的算法，但是我仍然完全迷失。進一步的幫助將不勝感激。 – IAQ 2012-02-27 01:57:31

Dijkstra算法的本質是它使用圖邊之間的一種傳遞閉包。例如，在第一次迭代中，您將看到，如果a - > b和b - > c，然後是a - > c，則基本上會繼續此操作，直到發現圖形中兩個節點之間存在路徑，或者嘗試所有可能的邊緣之間的不同方式，並發現沒有可能的路徑。布魯斯指出你在Scheme中實現這一點。 – 2012-02-27 02:04:22

查找路徑是否存在的最簡單方法是實施depth-first search。如果您在Scheme中執行了其他類型的遞歸編程，深度優先搜索將非常自然。這個想法是，對於每個節點，如果它是你完成的目的地;否則你會在每個孩子身上覆發。

唯一的問題是您需要跟蹤遍歷期間已經訪問過的節點，這樣可以避免兩次訪問同一個節點;否則如果你有一個圖A < - > B < - > C並且你正在檢查A是否連接到C，那麼你可能無限循環從A到B，然後B到A，然後A到B，永遠等等。

來源

2012-02-27 02:20:50 jacobm

查找無向圖路徑的算法

回答

相關問題