代码之家 › 专栏 › 技术社区 › Jonathan Sterling

从边列表构建图形

edges graph data-structures haskell

2

Jonathan Sterling · 技术社区 · 13 年前

给定的图形数据类型如下:

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 :~> [] ]
                ]

我确信它就在我的眼前,但我有点累了,很感激你的帮助。谢谢

2 回复 | 直到 13 年前

1

2

Landei 13 年前

查找起始节点:该节点显示在 map fst edges 列表中,但不在 map snd edges 列表正如luqui所说,你需要考虑没有找到这样一个节点的情况(或者如果你找到了不止一个)
从这个起始节点递归地构建树。小心,因为图中可能仍有循环

2

0

Stéphane Laurent 8 年前

不是你想要的,而是 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])]