haskell - Haskell Prim のアルゴリズム

Question

プリムのアルゴリズムを変更して、接続されていないグラフを処理する方法を知っている人はいますか? フォレストを使用する必要があることはわかっていますが、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 のアルゴリズムを個別に実行します。