mst

Documentation

Index

• type MST
  • func BuildKruskalMST(wg *graph.WeightGraph) MST
  • func BuildLazyPrimMST(wg *graph.WeightGraph) MST

Types

type MST

type MST interface {
	// Edges in the MST
	Edges() []graph.Edge
	// Weight gives the total weight of the MST
	Weight() float64
}

MST is the minimum spanning tree of a WeightedGraph. If the edges have unique weights, the MST will be unique. Otherwise, this MST is one of the MSTs for the graph.

func BuildKruskalMST

func BuildKruskalMST(wg *graph.WeightGraph) MST

BuildKruskalMST builds the MST for a weighted graph wg. This is O(E log E). If edges arrive sorted, E log V.

func BuildLazyPrimMST

func BuildLazyPrimMST(wg *graph.WeightGraph) MST

BuildLazyPrimMST builds the MST for a weighted graph wg. This is O(E log E) and extra space proportional to E.