在 Haskell 中实现 Prim 算法

Question

我在执行 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。

Answer 1

我认为问题在于您的 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 是 (vertex, weight) 对所有定向的列表，外向箭头从 visited 中的任何地方设置为一些other vertex（可能包括一些指向访问集中已经存在的 vertexes 的箭头）。

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

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

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

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

在 Haskell 中实现 Prim 算法

Implementing Prim's algorithm in Haskell

haskell

graph-theory

minimum-spanning-tree

prims-algorithm