我需要在給定邊緣的情況下找到圖的連通分量。
圖邊表示為元組串列，結果需要是表示連接組件的頂點串列串列，例如[(1,2), (2,3), (2,6), (5,6) (6,7), (8,9), (9,10)] -> [[1,2,3,5,6,7], [8,9,10]]。串列中可能有任意數量的連接邊和未連接的圖組件。但是，如果有幫助，元組將始終按升序排列。
我有簽名groupEdges :: [(Int, Int)] -> [[Int]]，但我只是想不出如何從元組到串列。
我想一次取一個元組并搜索其余的匹配元素，但我不知道如何制作這個子串列串列。
這個問題類似于CS Stack Exchange上的這個問題，但我不想使用 Data.Graph。如果可能的話，我想在沒有其他軟體包的情況下這樣做。
-- 編輯- chepner 和 ThibautM 的評論讓我邁出了第一步。我可以通過呼叫函式將元組轉換為串列groupEdges map (\(x,y) -> [x,y]) pairs。
現在我需要獲取這個串列串列并將連接的組件分組，例如。[[1,2], [2,3], [2,6], [5,6], [6,7], [8,9], [9,10]] -> [[1,2,3,5,6,7], [8,9,10]]
uj5u.com熱心網友回復：
你提到不使用包。如果你真的想要，我使用的 4 個函式相對容易實作。（我鼓勵你要么這樣做，要么至少查找他們的實作）
串列作為集合使用，這在性能上比使用專用結構（例如 Data.Set）要差得多。使用不相交集（聯合查找，合并查找）資料結構（在您的鏈接答案中參考）會更好，但作為理解的起點可能不是很好
import Data.List (elem, intersect, union, partition)
pairs = [(1,2), (2,3), (2,6), (5,6), (6,7), (8,9), (9,10)]
pairs2 = map (\(x,y) -> [x,y]) pairs
-- add item to list, only if its no already present - using list as set
addItem item list | elem item list = list
| otherwise = item : list
-- used to test whether subgraphs are connected i.e. contain common node
intersects a b = not $ null $ intersect a b
unionAll :: (Eq a) => [[a]] -> [a]
unionAll (x1:x2:xs) = unionAll ((union x1 x2):xs)
unionAll [x] = x
unionAll [] = []
-- find edges that are connected to first edge/subgraph and merge them
groupFirst :: (Eq a) => [[a]] -> [[a]]
groupFirst (x:xs) = (unionAll (x:connected)) : disconnected
where
-- separate 'xs' edges/subgraphs into those that are connected to 'x' and the rest
(connected, disconnected) = partition (intersects x) xs
groupFirst [] = []
-- if no more edges/subgraphs can be connected with first edge, continue with remaining (disconnected) edge/subgraph ([5,6] in second iteration)
groupAll :: (Eq a) => [[a]] -> [[a]]
groupAll (x:xs) = y:(groupAll ys)
where
(y:ys) = groupFirst (x:xs)
groupAll [] = []
-- after first 'groupAll pairs2' - [[1,2,3,6],[5,6,7],[8,9,10]]
-- repeat this process until no more components can be connected together
groupAllRepeat x = if x /= groupAll x then groupAllRepeat (groupAll x) else x
main = print (groupAllRepeat pairs2)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/462818.html
標籤：哈斯克尔