Haskell Prim 算法

Question

有谁知道如何更改 prim 的算法以便处理未连接的图？我知道我必须使用森林，但我不知道如何在 Haskell 中实现它。

Answer 1

`这就是我得到的

prim for            = prim' [n] ns [[]]
    where (n:ns)    = nodes for
        es          = edges for
        prim' t [] mst        = mst
        prim' t (r:rs) (x:xs) = let m = minimum[(c,u',v'| u <-t, v <- (r:rs), (u,v,c) <- es]
                    m | m == Nothing    = prim' (r:t) rs ([]:mst)
                      | otherwise       = prim' (v:t) (delete v' r) ((m:x):xs)

Answer 2

Prim 的算法找到了 MST，但如果图未连接，则不存在 MST。您可以检查您的树是否是生成树（如果它具有 |V|） - 1 个元素。

Answer 3

很容易找到图形的连接部分。分别对每个连接的子图运行 Prim 算法。