mst

Documentation

Index

• Constants
• func BoruvkaMST(g *graphs.WeightedGraph) (mst *graphs.WeightedGraph)
• func KruskalMST(g *graphs.WeightedGraph) (mst *graphs.WeightedGraph)
• func PrimMST(g *graphs.WeightedGraph) (mst *graphs.WeightedGraph)
• type DSU
  • func NewDSU(n int) DSU
  • func (dsu *DSU) Find(v int) int
  • func (d *DSU) Size(v int) int
  • func (dsu *DSU) Union(v1, v2 int)
• type MSTAlogorithm
• type Node
• type PriorityQueue
  • func NewPQ[V comparable, P constraints.Ordered]() *PriorityQueue[V, P]
  • func (pq *PriorityQueue[V, P]) Contains(value V) bool
  • func (pq *PriorityQueue[V, P]) IsEmpty() bool
  • func (pq *PriorityQueue[V, P]) Len() int
  • func (pq *PriorityQueue[V, P]) Less(i int, j int) bool
  • func (pq *PriorityQueue[V, P]) Pop() any
  • func (pq *PriorityQueue[V, P]) Push(node any)
  • func (pq *PriorityQueue[V, P]) Swap(i int, j int)
  • func (pq *PriorityQueue[V, P]) Update(value V, priority P)

Constants

const NO_CC = -1

const NO_PARENT_ID = -1

const NO_PARENT_ID_PRIM = -1

const START_VERTEX_INDEX = 0

Functions

func BoruvkaMST

func BoruvkaMST(g *graphs.WeightedGraph) (mst *graphs.WeightedGraph)

func KruskalMST

func KruskalMST(g *graphs.WeightedGraph) (mst *graphs.WeightedGraph)

func PrimMST

func PrimMST(g *graphs.WeightedGraph) (mst *graphs.WeightedGraph)

Types

type DSU

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

func NewDSU

func NewDSU(n int) DSU

func (*DSU) Find

func (dsu *DSU) Find(v int) int

func (*DSU) Size

func (d *DSU) Size(v int) int

func (*DSU) Union

func (dsu *DSU) Union(v1, v2 int)

type MSTAlogorithm

type MSTAlogorithm func(g *graphs.WeightedGraph) *graphs.WeightedGraph

type Node

type Node[V comparable, P constraints.Ordered] struct {
	Value    V
	Priority P
}

type PriorityQueue

type PriorityQueue[V comparable, P constraints.Ordered] struct {
	// contains filtered or unexported fields
}

func NewPQ

func NewPQ[V comparable, P constraints.Ordered]() *PriorityQueue[V, P]

func (*PriorityQueue[V, P]) Contains

func (pq *PriorityQueue[V, P]) Contains(value V) bool

func (*PriorityQueue[V, P]) IsEmpty

func (pq *PriorityQueue[V, P]) IsEmpty() bool

func (*PriorityQueue[V, P]) Len

func (pq *PriorityQueue[V, P]) Len() int

func (*PriorityQueue[V, P]) Less

func (pq *PriorityQueue[V, P]) Less(i int, j int) bool

Less implements heap.Interface.

func (*PriorityQueue[V, P]) Pop

func (pq *PriorityQueue[V, P]) Pop() any

Pop implements heap.Interface.

func (*PriorityQueue[V, P]) Push

func (pq *PriorityQueue[V, P]) Push(node any)

func (*PriorityQueue[V, P]) Swap

func (pq *PriorityQueue[V, P]) Swap(i int, j int)

Swap implements heap.Interface.

func (*PriorityQueue[V, P]) Update

func (pq *PriorityQueue[V, P]) Update(value V, priority P)