Haskell中的圖形表示

我選擇用節點列表（例如n=[1,2,3,4]）和表示邊緣的對列表（示例m=[(1,2), (2,3)]）在Haskell中表示圖形。現在我必須看看圖表是否強連接。Haskell中的圖形表示

我的主要問題是如何找到圖中2個節點之間是否有方法。我寫了這樣的事情：

-- sees if 2 nodes are adjacent 

adjacent x y [] = False 

adjacent x y (mu:m) = 
     if(x== (fst mu) && y==(snd mu)) then True 
     else adjacent x y m 

-- the successor of a node, ex for the edge (1,2) the succ of 1 is 2 
suc x [] = 0 
suc x (l:list) = 
     if(x==(fst l)) then snd l 
     else suc x list 

-- my main function 
way 0 y list = False 

way x y (mu:m) 
    | x==y = True 
    | (adjacent x y (mu:m)) == True = True 
    | otherwise = 
     if ((way (suc x (mu:m)) y (mu:m))==False) then way (suc x m) y m 
     else True

它工作時，我有1度節點，但對於具有更大程度的節點並不總是工作。你能給我一些線索嗎？

來源

2010-05-05 anna-k

+1爲是明確它是家庭作業！讓我們知道如何接近幫助。 – MtnViewMark 2010-05-05 20:28:59

一旦某個特定答案幫助您成功解決了您的問題，選擇它就很正常（點擊投票計數下的複選標記），以便知道問題已解決。向成員表明他們現在可能想花時間處理其他問題。 – MtnViewMark 2010-05-06 13:13:18

你必須瞭解兩個錯誤：

m，您邊緣的名單是在整個搜索靜態的。當你在way中再次發生時，不要吃它。
每個頂點可以有多於一個的邊緣。你想知道x的鄰居any是否有y爲way。要找到您首先需要的鄰居filter邊緣列表才能找到只留下x的邊。

您還需要建立一個您已經訪問過的節點列表，以查找連接。如果你最終在一個你已經看到的節點上，那麼這條特定路徑失敗了。

一些提示使您的代碼縮短了很多：對於adjacent，請嘗試elem。對於succ，請嘗試Data.Maybe.fromMaybe和lookup。

來源

2010-05-05 20:22:05

這裏有一些問題要問自己：

應該adjacent 3 2 [(1,2),(2,3)]是True？
多少接班人1圖中的[(1,2),(2,3),(1,4),(3,4)]
爲什麼有呢，還是沒有，way需要同時擁有x==y情況和adjacent x y ...情況？
在way的遞歸步驟== False測試是否真的告訴你一些東西，可以讓你在m的較小圖上遞歸？

通常，您還沒有爲您的頂級功能編寫類型簽名。它通常是非常有啓發這樣做，而且會更清楚地傳達你的設計：

type Vertex = Int 
type Edge = (Vertex, Vertex) 
type Graph = [Edge] 

adjacent :: Vertex -> Vertex -> Graph -> Bool 
suc :: Vertex -> Graph -> Vertex 
way :: Vertex -> Vertex -> Graph -> Bool

想想如果這些類型的意義，如果他們分解你的問題，因爲你所期望的，只是想着在一般的圖。

你的目標真的是way函數，還是它確定圖形是否連接？您可能會過多地預測圖表是否已連接。

最後，關於Haskell語法的一小部分：與大多數其他語言一樣，函數應用程序綁定得非常緊密，比==和&&運算符更緊密。與大多數其他語言不同，函數應用程序不使用括號。因此，adjacent可以重新編碼爲：

adjacent x y [] = False 
adjacent x y (mu:m) = 
    if x == fst mu && y == snd mu then True 
    else adjacent x y m

這反過來又可以簡化爲：

adjacent x y [] = False 
adjacent x y (mu:m) = (x == fst mu && y == snd mu) || adjacent x y m

來源

2010-05-05 20:26:05 MtnViewMark

感謝您的意見，他們歡迎。我已修改，現在它的作品！ – 2010-05-06 12:49:36

Haskell中的圖形表示

回答

相關問題