从边列表中查找连接的组件

Question

我需要在给定边的情况下找到图的连通分量。

图的边表示为元组列表，结果需要是表示连通分量的顶点列表列表，例如 [(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 上的 this question 相似，但我不想使用 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]]

Answer 1

您提到不使用包。如果你真的想要的话，我使用的 4 个功能是相对容易实现的。（我鼓励你要么这样做，要么至少查看它们的实现）

列表作为集合使用，这在性能上比使用专用结构差很多，例如Data.Set。使用 disjoint-set (union-find, merge-find) 数据结构（在您的链接答案中引用）会更好，但作为理解

的起点可能不是很好

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)

从边列表中查找连接的组件

Find connected components from lists of edges

haskell