haskell - 从边列表构建图

Question

给定一个图形数据类型如下：

data Graph = Int :~> [Graph]
infixr :~>

和这样的边缘列表：

edges = [(10,1), (10,5), (1,2), (2,3), (5,6), (5,9), (9,8)]

将构建图形的函数如下：

result = 10 :~> [ 1 :~> [ 2 :~> 3 :~> [] ] 
                , 5 :~> [ 6 :~> [], 9 :~> 8 :~> [] ]
                ]

我确信它就在我的脑海中，但我有点筋疲力尽，希望能得到帮助。谢谢！

Answer 1

1. 查找起始节点：该节点出现在map fst edges列表中但不在map snd edges列表中。正如 luqui 所说，您需要考虑找不到这样一个节点（或者如果您找到多个节点）的情况
2. 从这个起始节点递归地构建你的树。小心，因为你仍然可以在图中有循环

Answer 2

不是您真正想要的，但库的Data.Graph模块containers可以提供帮助。

import Data.Graph
bounds = (1,10) 
edges = [(10,1), (10,5), (1,2), (2,3), (5,6), (5,9), (9,8)]

> buildG bounds edges
array (1,10) [(1,[2]),(2,[3]),(3,[]),(4,[]),(5,[9,6]),(6,[]),(7,[]),(8,[]),(9,[8]),(10,[5,1])]