时间戳

首页 > 解决方案 > 在 Haskell 中实现 Prim 算法

haskell - 在 Haskell 中实现 Prim 算法

问题描述

我在实现 prim 算法时遇到了困难，我的逻辑很错误，这就是我到目前为止得到的：

import Data.Array
import Data.Function (on)
import Data.List (sortBy, delete)

type Vertex = Int
type Weight = Int
type Graph  = Array Vertex [(Vertex, Weight)]
type Bounds = (Vertex, Vertex)
type Edge   = (Vertex, Vertex, Weight)

g1 = mkGraph (1, 4) [(1, 2, 1), (1, 3, 10), (1, 4, 3), (2, 3, 4), (2, 4, 10), (3, 4, 1)] -- 5
g2 = mkGraph (1, 5) [(1, 2, 15), (1, 3, 10), (2, 3, 1), (3, 4, 3), (2, 4, 5), (4, 5, 20)] -- 34

mkGraph :: Bounds -> [Edge] -> Graph
mkGraph bounds edges = accumArray (\xs x -> x:xs) [] bounds [ (x, (y, w)) | (x, y, w) <- edges]

--[(1,[(4,3),(3,10),(2,1)]),(2,[(4,10),(3,4)]),(3,[(4,1)]),(4,[])]
prim :: Graph -> Vertex -> [(Vertex, Weight)]
prim graph start = prim' (sortBy (compare `on` snd) (graph ! start)) [start] []
    where
        prim' [] _ mst = mst
        prim' (x:xs) visited mst
            | elem (fst x) visited = prim' xs visited mst
            | otherwise            = prim' (delete x $ sortBy (compare `on` snd) ((graph ! (fst x)) ++ xs)) ((fst x):visited) (x:mst)

我的想法是，如果我把从顶点开始可能到达的每条边（假设是 1）选择最小值（在这种情况下是该列表中的第一个元素，因为它已排序），则选择它的第一个元素元组并将其用作索引，并使所有边都可以从该顶点到达，同时添加从前一个顶点可到达的顶点。

在跟踪访问的顶点时，问题是如果它到达最终顶点（它将是空的），那么它将停止添加边并且将仅使用已经添加的边。

但这也不起作用，因为我一直跟踪访问的顶点的方式会跳过类似 [(1, 3, 10) (2, 3, 1)] 的内容，因为它会将顶点 3 标记为已访问。

标签： haskellgraph-theoryminimum-spanning-treeprims-algorithm

解决方案

我认为问题在于您Graph作为数组的表示是隐含的“有向”，因此您需要获取输入的无向图并在两个方向上制表边：

mkGraph :: Bounds -> [Edge] -> Graph
mkGraph bounds edges = accumArray (\xs x -> x:xs) [] bounds 
    [(x, (y, w)) | (x', y', w) <- edges, (x, y) <- [(x', y'), (y', x')]]

现在，递归的不变量是：

prim' outgoing visited mst

参数是从集合中的任何地方到另一个的所有有向、传出箭头对outgoing的列表（可能包括一些指向已访问集合中的 es 的箭头）。(vertex, weight)visitedvertexvertex

在每个递归步骤中，您将任何此类传出箭头跳过到您已经访问过的顶点，并且当您找到具有最小权重的未访问顶点时，将该边添加到您的mst中，将未访问的顶点添加到那些中visited，并增加outgoing箭头集从新访问的顶点发出的任何箭头。

（在您的代码中，您delete x虽然没有技术上的需要这样做，因为它将作为“已访问”检查的一部分被过滤掉。）

将上述更改为mkGraph，您prim似乎可以在 、 和图表上正常g1工作g2：

g3 = mkGraph (1,3) [(1,3,10), (2,3,1)]

推荐阅读