Safe Haskell	None
Language	Haskell2010

Kruskal

Description

Kruskal's algorithm

An algorithm to find the minimum spanning forest of an edge-weighted graph.

Sources:

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
Joseph B. Kruskal, "On the shortest spanning subtree of a graph and the traveling salesman problem", 1956 https://www.ams.org/journals/proc/1956-007-01/S0002-9939-1956-0078686-7/

Synopsis

data WEdge = WEdge {
- getU :: !Vertex
- getV :: !Vertex
- getW :: !Weight
}
type Weight = Int
kruskal :: Bounds -> [WEdge] -> [WEdge]

Documentation

data WEdge Source #

Constructors

WEdge
Fields getU :: !Vertex getV :: !Vertex getW :: !Weight

Instances

Instances details

Eq WEdge Source #
Instance details Defined in Kruskal Methods (==) :: WEdge -> WEdge -> Bool # (/=) :: WEdge -> WEdge -> Bool #
Show WEdge Source #
Instance details Defined in Kruskal Methods showsPrec :: Int -> WEdge -> ShowS # show :: WEdge -> String # showList :: [WEdge] -> ShowS #
NFData WEdge Source #
Instance details Defined in Kruskal Methods rnf :: WEdge -> () #

type Weight = Int Source #

kruskal :: Bounds -> [WEdge] -> [WEdge] Source #

Runs Kruskal's algorithm on the graph represented by the given list of edges. Returns the edges that are part of a minimum spanning forest. Vertices should be non-negative. O(|V| + |E|log|E|).