Minimum Spanning Tree (MST)

A Minimum Spanning Tree (MST) of a graph is a subset of the edges that connects all vertices in the graph without any cycles and with the minimum possible total edge weight. Two classic algorithms for finding the MST are Kruskal's and Prim's algorithms.

1. Kruskal's Algorithm

Kruskal's algorithm builds the MST by adding edges in increasing order of their weights, ensuring that no cycles are formed.

Implementation:

1. Sort all the edges in non-decreasing order of their weight.
2. Initialize a forest where each vertex is a separate tree.
3. Iterate through the sorted edges and add the edge to the MST if it doesn't form a cycle.

Code:

go
package main

import (
	"fmt"
	"sort"
)

// Edge represents an edge in the graph
type Edge struct {
	u, v, weight int
}

// Union-Find data structure
type UnionFind struct {
	parent, rank []int
}

// NewUnionFind creates a new Union-Find data structure
func NewUnionFind(n int) *UnionFind {
	uf := &UnionFind{
		parent: make([]int, n),
		rank:   make([]int, n),
	}
	for i := range uf.parent {
		uf.parent[i] = i
	}
	return uf
}

// Find finds the root of the set containing x
func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x]) // Path compression
	}
	return uf.parent[x]
}

// Union joins the sets containing x and y
func (uf *UnionFind) Union(x, y int) {
	rootX := uf.Find(x)
	rootY := uf.Find(y)
	if rootX != rootY {
		if uf.rank[rootX] > uf.rank[rootY] {
			uf.parent[rootY] = rootX
		} else if uf.rank[rootX] < uf.rank[rootY] {
			uf.parent[rootX] = rootY
		} else {
			uf.parent[rootY] = rootX
			uf.rank[rootX]++
		}
	}
}

// Kruskal finds the MST using Kruskal's algorithm
func Kruskal(edges []Edge, n int) []Edge {
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})

	uf := NewUnionFind(n)
	var mst []Edge

	for _, edge := range edges {
		if uf.Find(edge.u) != uf.Find(edge.v) {
			mst = append(mst, edge)
			uf.Union(edge.u, edge.v)
		}
	}

	return mst
}

func main() {
	edges := []Edge{
		{0, 1, 10}, {0, 2, 6}, {0, 3, 5},
		{1, 3, 15}, {2, 3, 4},
	}
	n := 4 // Number of vertices
	mst := Kruskal(edges, n)
	fmt.Println("Edges in the Minimum Spanning Tree:")
	for _, edge := range mst {
		fmt.Printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight)
	}
}

2. Prim's Algorithm

Prim's algorithm builds the MST by starting with an arbitrary vertex and growing the MST one edge at a time by adding the cheapest edge from the tree to a vertex not yet in the tree.

Implementation:

1. Initialize the MST with a single vertex (arbitrary choice).
2. Use a priority queue to keep track of the minimum weight edge crossing the cut.
3. At each step, add the minimum weight edge from the priority queue to the MST.

Code:

go
package main

import (
	"container/heap"
	"fmt"
)

// Edge represents an edge in the graph
type Edge struct {
	v, weight int
}

// Item is something we manage in a priority queue.
type Item struct {
	node, weight int
	index        int
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].weight < pq[j].weight
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

// Prim finds the MST using Prim's algorithm
func Prim(graph map[int][]Edge, start int) []Edge {
	mst := []Edge{}
	visited := make(map[int]bool)
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, &Item{node: start, weight: 0})

	for pq.Len() > 0 {
		item := heap.Pop(pq).(*Item)
		u := item.node
		if visited[u] {
			continue
		}
		visited[u] = true
		if item.weight != 0 { // Skip the first zero-weight edge
			mst = append(mst, Edge{v: u, weight: item.weight})
		}

		for _, edge := range graph[u] {
			if !visited[edge.v] {
				heap.Push(pq, &Item{node: edge.v, weight: edge.weight})
			}
		}
	}

	return mst
}

func main() {
	graph := map[int][]Edge{
		0: {{1, 10}, {2, 6}, {3, 5}},
		1: {{0, 10}, {3, 15}},
		2: {{0, 6}, {3, 4}},
		3: {{0, 5}, {1, 15}, {2, 4}},
	}
	start := 0
	mst := Prim(graph, start)
	fmt.Println("Edges in the Minimum Spanning Tree:")
	for _, edge := range mst {
		fmt.Printf("%d -- %d == %d\n", start, edge.v, edge.weight)
	}
}

Summary

• Kruskal's Algorithm: Efficient for sparse graphs, sorts edges and uses a union-find data structure to detect cycles.
• Prim's Algorithm: Efficient for dense graphs, uses a priority queue to select the smallest edge connecting the MST to a new vertex.

Both algorithms are fundamental in finding MSTs and have their own advantages depending on the graph's properties. Understanding these algorithms and their implementations can greatly enhance a Go developer's ability to handle graph-related problems efficiently.