Documentation ¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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.
Click to show internal directories.
Click to hide internal directories.