Алгоритм Хаскеля Прима

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

Легко найти связанные части графика.Запустите алгоритм Прима для каждого связного подграфа отдельно.

Answer 3

Алгоритм Прима находит MST, но если граф не связан, MST не существует. Вы можете проверить, является ли ваше дерево связующим, если оно имеет | V | - 1 элементов это в.