kruskal

Documentation

Overview

Package provides an implementation of the Kruskal's minimum spanning forest algorithm together with an implementation of disjoint set data structure

Index

• type Edge
  • func MinimumSpanningForest(n int, edges []Edge) []Edge
• type Edges
  • func (edges Edges) Len() int
  • func (edges Edges) Less(i, j int) bool
  • func (edges Edges) Swap(i, j int)
• type Node
  • func Find(node *Node) *Node
  • func Union(a, b *Node) *Node

Types

type Edge

type Edge struct {
	// contains filtered or unexported fields
}

Type for edge data - endpoints u, v and length

func MinimumSpanningForest

func MinimumSpanningForest(n int, edges []Edge) []Edge

Computes the minimum spanning forest in a graph with vertices numbered from 0 to n-1 and a given set of edges. Returns the subset of edges forming the minimum spanning forest.

type Edges

type Edges []Edge

Type required for calling the sort.Sort method

func (Edges) Len

func (edges Edges) Len() int

func (Edges) Less

func (edges Edges) Less(i, j int) bool

func (Edges) Swap

func (edges Edges) Swap(i, j int)

type Node

type Node struct {
	// contains filtered or unexported fields
}

Type holding parent pointer and rank for a DSU node

func Find

func Find(node *Node) *Node

Recursive implementation of find with path compression

func Union

func Union(a, b *Node) *Node

Implementation of union with ranks, returns a node being the root of the new component