The Minimum Spanning Tree (MST) is a fundamental concept in graph theory with numerous applications, including network design, clustering, and approximation algorithms. Kruskal’s algorithm is one of the most efficient and widely used algorithms to find the MST of a connected, undirected graph. This article provides a comprehensive guide to implementing Kruskal’s algorithm in Go, complete with detailed explanations and well-documented code.

Problem Statement

Given a connected, undirected graph with weighted edges, the goal is to find a subset of the edges that forms a tree including every vertex, where the total weight of all the edges in the tree is minimized. This subset is known as the Minimum Spanning Tree (MST).

Program Structure

The Go program to find the MST using Kruskal’s algorithm is structured as follows:

• Edge Representation: Each edge is represented with its source, destination, and weight.
• Graph Initialization: The graph is initialized by adding all edges.
• Union-Find Data Structure: Used to detect cycles and manage disjoint sets.
• Kruskal’s Algorithm Implementation: The algorithm sorts all edges and selects the smallest edge that doesn’t form a cycle until the MST is formed.
• Main Function: Demonstrates the usage of the MST implementation with an example graph.

Go Program

package main

import (
    "fmt"
    "sort"
)

// Edge represents a weighted edge in the graph
type Edge struct {
    src, dest, weight int
}

// Graph represents a graph with vertices and edges
type Graph struct {
    vertices int
    edges    []Edge
}

// NewGraph initializes a new graph with a given number of vertices
func NewGraph(vertices int) *Graph {
    return &Graph{
        vertices: vertices,
        edges:    []Edge{},
    }
}

// AddEdge adds an edge to the graph
func (g *Graph) AddEdge(src, dest, weight int) {
    g.edges = append(g.edges, Edge{src, dest, weight})
}

// UnionFind represents the Union-Find data structure for cycle detection
type UnionFind struct {
    parent []int
    rank   []int
}

// NewUnionFind initializes a new Union-Find structure
func NewUnionFind(size int) *UnionFind {
    uf := &UnionFind{
        parent: make([]int, size),
        rank:   make([]int, size),
    }
    for i := 0; i < size; i++ {
        uf.parent[i] = i
        uf.rank[i] = 0
    }
    return uf
}

// Find finds the root of the set in which element k is present
func (uf *UnionFind) Find(k int) int {
    if uf.parent[k] != k {
        uf.parent[k] = uf.Find(uf.parent[k]) // Path compression
    }
    return uf.parent[k]
}

// Union unites the sets that include x and y
func (uf *UnionFind) Union(x, y int) bool {
    xroot := uf.Find(x)
    yroot := uf.Find(y)

    if xroot == yroot {
        return false // Cycle detected
    }

    // Union by rank
    if uf.rank[xroot] < uf.rank[yroot] { uf.parent[xroot] = yroot } else if uf.rank[xroot] > uf.rank[yroot] {
        uf.parent[yroot] = xroot
    } else {
        uf.parent[yroot] = xroot
        uf.rank[xroot]++
    }
    return true
}

// KruskalMST implements Kruskal's algorithm to find the MST
func (g *Graph) KruskalMST() []Edge {
    var result []Edge

    // Step 1: Sort all edges in non-decreasing order of their weight
    sort.Slice(g.edges, func(i, j int) bool {
        return g.edges[i].weight < g.edges[j].weight
    })

    // Step 2: Initialize Union-Find
    uf := NewUnionFind(g.vertices)

    // Step 3: Iterate through sorted edges and select edges that don't form a cycle
    for _, edge := range g.edges {
        if uf.Union(edge.src, edge.dest) {
            result = append(result, edge)
            // If we've included enough edges, we can stop
            if len(result) == g.vertices-1 {
                break
            }
        }
    }

    return result
}

func main() {
    // Example usage:
    // Create a graph with 4 vertices
    g := NewGraph(4)

    // Add edges to the graph
    g.AddEdge(0, 1, 10)
    g.AddEdge(0, 2, 6)
    g.AddEdge(0, 3, 5)
    g.AddEdge(1, 3, 15)
    g.AddEdge(2, 3, 4)

    // Find the MST using Kruskal's algorithm
    mst := g.KruskalMST()

    fmt.Println("Edges in the Minimum Spanning Tree:")
    totalWeight := 0
    for _, edge := range mst {
        fmt.Printf("(%d - %d) with weight %d\n", edge.src, edge.dest, edge.weight)
        totalWeight += edge.weight
    }
    fmt.Printf("Total Weight of MST: %d\n", totalWeight)
}
    

Documentation

The Go program provided implements Kruskal’s algorithm to find the Minimum Spanning Tree (MST) of a connected, undirected graph. Below is a detailed explanation of each component of the program:

1. Edge Struct

The Edge struct represents a weighted edge in the graph, containing the source vertex src, destination vertex dest, and the weight of the edge.

2. Graph Struct and Methods

The Graph struct encapsulates the graph’s structure, including the number of vertices and a slice of edges.

NewGraph Function

The NewGraph function initializes a new graph with a specified number of vertices and an empty slice of edges.

AddEdge Method

The AddEdge method allows adding an edge to the graph by specifying the source vertex, destination vertex, and the edge’s weight.

3. UnionFind Struct and Methods

The UnionFind struct implements the Union-Find (Disjoint Set) data structure, which is essential for detecting cycles in Kruskal’s algorithm.

NewUnionFind Function

The NewUnionFind function initializes the Union-Find structure with each vertex as its own parent and rank set to 0.

Find Method

The Find method determines the root parent of a given vertex k, implementing path compression for optimization.

Union Method

The Union method merges the sets containing vertices x and y. It returns true if the union is successful (no cycle is formed) and false otherwise.

4. KruskalMST Method

The KruskalMST method implements Kruskal’s algorithm to find the MST:

1. Sorting Edges: All edges are sorted in non-decreasing order of their weights.
2. Initializing Union-Find: A Union-Find structure is initialized to manage disjoint sets.
3. Selecting Edges: The algorithm iterates through the sorted edges, selecting the smallest edge that doesn’t form a cycle and adding it to the MST.
4. Termination: The process continues until the MST contains vertices - 1 edges.

5. Main Function

The main function demonstrates the usage of the MST implementation:

1. A graph with 4 vertices is created.
2. Edges with specified weights are added to the graph.
3. Kruskal’s algorithm is executed to find the MST.
4. The edges in the MST and the total weight are printed.

How the Program Works

1. Graph Initialization: The program starts by creating a new graph with a specified number of vertices using the NewGraph function.
2. Adding Edges: Edges are added to the graph using the AddEdge method, specifying the source, destination, and weight of each edge.
3. Kruskal’s Algorithm:
   • All edges are sorted based on their weights in ascending order.
   • A Union-Find structure is initialized to keep track of connected components and detect cycles.
   • The algorithm iterates through the sorted edges, adding each edge to the MST if it doesn’t form a cycle.
   • This process continues until the MST includes vertices - 1 edges.
4. Output: The program prints the edges included in the MST along with the total weight of the MST.

Example Output

Given the following graph with 4 vertices and edges:

• Edge between vertex 0 and 1 with weight 10
• Edge between vertex 0 and 2 with weight 6
• Edge between vertex 0 and 3 with weight 5
• Edge between vertex 1 and 3 with weight 15
• Edge between vertex 2 and 3 with weight 4

Running the program produces the following output:

Edges in the Minimum Spanning Tree:
(2 - 3) with weight 4
(0 - 3) with weight 5
(0 - 1) with weight 10
Total Weight of MST: 19
    

This output indicates that the MST includes the edges (2-3), (0-3), and (0-1) with a total weight of 19.

Conclusion

Kruskal’s algorithm is an efficient method for finding the Minimum Spanning Tree of a connected, undirected graph. By leveraging the Union-Find data structure for cycle detection and sorting edges by weight, the algorithm ensures that the MST is both optimal and correctly constructed. The provided Go implementation is well-documented and serves as a practical example for understanding and applying Kruskal’s algorithm in real-world scenarios.

Excerpt

Discover how to implement Kruskal’s algorithm in Go to find the Minimum Spanning Tree of a graph. Detailed explanations and well-documented code included.