無向圖的深度優先搜索（DFS）

-1

如果給我一個包含邊數（圖），邊對數，原點和目的地的列表，我將如何確定是否存在路徑？

我有一些想法，但只需要在計劃啓動方面一點幫助。

(is_it_a_path? '(4 ((1 2) (2 3) (3 4) (2 4))) 1 4) ; returns true 

(is_it_a_path? '(3 ((1 2) (2 3) (3 1))) 2 3)  ; also returns true

在下面的圖4是頂點的數目，（1 2）...等是有邊緣和1是開始和4是端。基本上，從下面定義的圖中可以看出是否存在從1到4的路徑。我希望能澄清我的意思。

2012-02-24 A_1_615

[無向圖路徑]的可能重複（http://stackoverflow.com/questions/9402362/undirected-graph-path） – 2012-02-24 07:44:56

是請忽略另一個問題....它沒有被正確解釋... 。我無法刪除它。 – 2012-02-24 07:45:53

但是......你還沒有澄清我建議你在回答你的其他問題時澄清的事情嗎？圖表的數據定義是什麼？你有目標聲明，合同還是更簡單的/其他的例子？我仍然認爲我對這個問題的回答對於這個問題來說是合理的:)。 – 2012-02-24 17:03:56

您是否看到約翰克萊門茨的早期迴應，看看如何設計程序？它有一個Chapter關於如何設計處理圖的程序。

作爲一個元回答：您所問的問題，關於如何開始處理您不熟悉的問題，是HtDP書的核心。你看過嗎？它基本上是Polya的「如何解決它」的改編，但是專門用於編寫計算機程序而不是數學證明。 Second edition草案可能更易於閱讀。

2012-02-25 20:14:21 dyoo

回答