kruskal

package

v0.0.0-...-5aae7fa Latest Latest Go to latest Published: Nov 21, 2022 License: MIT Imports: 1 Imported by: 0

Details

Valid go.mod file
Redistributable license
Tagged version
Stable version
Learn more about best practices

Repository

git.colasdn.top/ch3ck/algo

Links

Open Source Insights

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
type Node
- func Find(node *Node) *Node
- func Union(a, b *Node) *Node

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

This section is empty.

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

Source Files ¶

dsu.go
kruskal.go

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL