Kruskal's Algorithm

Definition

Definition

Kruskal's Algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph. It works by selecting edges in increasing order of weight until all vertices are connected without forming a cycle

Explanation

Create an empty graph which will eventually represent the Minimum Spanning Tree (MST). Next, arrange all edges of the graph in ascending order based on their weights. Then, proceed to traverse through these sorted edges. During each iteration, evaluate if including the current edge into the MST introduces a cycle; if not, incorporate it into the MST. This process repeats until all vertices in the graph are interconnected within the MST

Guidance

• Sort all edges of the graph in non-decreasing order of weight
• Initialize an empty MST
• Iterate through the sorted edges
• If adding the current edge to the MST does not form a cycle, add it to the MST
• Use a disjoint-set data structure to detect cycles
• Continue until all vertices are connected in the MST
• Return the MST

Tips

• use a disjoint-set data structure (such as Union-Find) to efficiently detect cycles
• always prioritize edges with the smallest weights to ensure the resulting MST is minimal
• implement efficient sorting algorithms, such as merge sort or quicksort, to sort the edges

Practice

Practice

kruskalMST(graph):
    edges = graph.getAllEdges() // Retrieve all edges from the graph
    edges.sort() // Sort edges in non-decreasing order of weight
    MST = new Graph() // Initialize an empty graph to hold the MST
    disjointSet = new DisjointSet() // Initialize a disjoint-set data structure

    for edge in edges:
        if !disjointSet.isSameSet(edge.start, edge.end):
            // Adding this edge does not form a cycle
            MST.addEdge(edge.start, edge.end, edge.weight) // Add edge to the MST
            disjointSet.union(edge.start, edge.end) // Union the sets of the vertices

        if MST.numEdges == MST.numVertices - 1:
            break // MST is complete when all vertices are connected

    return MST

Solution

package main

import (
    "sort"
)

type Edge struct {
    Source, Destination, Weight int
}

type Graph struct {
    Vertices, Edges int
    EdgeList        []Edge
}

func (g *Graph) addEdge(src, dest, weight int) {
    g.EdgeList = append(g.EdgeList, Edge{src, dest, weight})
}

type UnionFind struct {
    parent []int
}

func newUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    for i := range parent {
        parent[i] = i
    }
    return &UnionFind{parent}
}

func (uf *UnionFind) find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) union(x, y int) {
    rootX := uf.find(x)
    rootY := uf.find(y)
    uf.parent[rootX] = rootY
}

func kruskals(g *Graph) []Edge {
    var result []Edge
    sort.Slice(g.EdgeList, func(i, j int) bool {
        return g.EdgeList[i].Weight < g.EdgeList[j].Weight
    })

    uf := newUnionFind(g.Vertices)
    for _, edge := range g.EdgeList {
        if uf.find(edge.Source) != uf.find(edge.Destination) {
            uf.union(edge.Source, edge.Destination)
            result = append(result, edge)
        }
    }
    return result
}

import java.util.*;

class Edge implements Comparable<Edge> {

  int source, destination, weight;

  public Edge(int source, int destination, int weight) {
    this.source = source;
    this.destination = destination;
    this.weight = weight;
  }

  @Override
  public int compareTo(Edge compareEdge) {
    return this.weight - compareEdge.weight;
  }
}

class Graph {

  int vertices, edges;
  Edge[] edgeList;

  public Graph(int vertices, int edges) {
    this.vertices = vertices;
    this.edges = edges;
    edgeList = new Edge[edges];
  }

  public void addEdge(int source, int destination, int weight, int index) {
    edgeList[index] = new Edge(source, destination, weight);
  }
}

class KruskalsAlgorithm {

  public static int findParent(int[] parent, int vertex) {
    if (parent[vertex] != vertex) {
      parent[vertex] = findParent(parent, parent[vertex]);
    }
    return parent[vertex];
  }

  public static void union(int[] parent, int x, int y) {
    int rootX = findParent(parent, x);
    int rootY = findParent(parent, y);
    parent[rootX] = rootY;
  }

  public static List<Edge> kruskals(Graph graph) {
    List<Edge> result = new ArrayList<>();
    Arrays.sort(graph.edgeList);

    int[] parent = new int[graph.vertices];
    for (int i = 0; i < graph.vertices; i++) {
      parent[i] = i;
    }

    int edgeCount = 0;
    for (Edge edge : graph.edgeList) {
      if (edgeCount == graph.vertices - 1) {
        break;
      }

      int sourceParent = findParent(parent, edge.source);
      int destinationParent = findParent(parent, edge.destination);

      if (sourceParent != destinationParent) {
        result.add(edge);
        union(parent, sourceParent, destinationParent);
        edgeCount++;
      }
    }

    return result;
  }
}

class Edge {
  constructor(source, destination, weight) {
    this.source = source;
    this.destination = destination;
    this.weight = weight;
  }
}

class Graph {
  constructor(vertices, edges) {
    this.vertices = vertices;
    this.edges = edges;
    this.edgeList = [];
  }

  addEdge(source, destination, weight) {
    this.edgeList.push(new Edge(source, destination, weight));
  }
}

class KruskalsAlgorithm {
  static findParent(parent, vertex) {
    if (parent[vertex] !== vertex) {
      parent[vertex] = this.findParent(parent, parent[vertex]);
    }
    return parent[vertex];
  }

  static union(parent, x, y) {
    const rootX = this.findParent(parent, x);
    const rootY = this.findParent(parent, y);
    parent[rootX] = rootY;
  }

  static kruskals(graph) {
    const result = [];
    graph.edgeList.sort((a, b) => a.weight - b.weight);

    const parent = Array.from({ length: graph.vertices }, (_, i) => i);

    let edgeCount = 0;
    for (const edge of graph.edgeList) {
      if (edgeCount === graph.vertices - 1) {
        break;
      }

      const sourceParent = this.findParent(parent, edge.source);
      const destinationParent = this.findParent(parent, edge.destination);

      if (sourceParent !== destinationParent) {
        result.push(edge);
        this.union(parent, sourceParent, destinationParent);
        edgeCount++;
      }
    }

    return result;
  }
}

data class Edge(val source: Int, val destination: Int, val weight: Int)

class Graph(private val vertices: Int) {
    val edgeList = mutableListOf<Edge>()

    fun addEdge(source: Int, destination: Int, weight: Int) {
        edgeList.add(Edge(source, destination, weight))
    }
}

class KruskalsAlgorithm(private val graph: Graph) {
    private fun findParent(parent: IntArray, vertex: Int): Int {
        var v = vertex
        if (parent[v] != v) {
            parent[v] = findParent(parent, parent[v])
        }
        return parent[v]
    }

    private fun union(parent: IntArray, x: Int, y: Int) {
        val rootX = findParent(parent, x)
        val rootY = findParent(parent, y)
        parent[rootX] = rootY
    }

    fun kruskals(): List<Edge> {
        val result = mutableListOf<Edge>()
        graph.edgeList.sortBy { it.weight }

        val parent = IntArray(graph.vertices) { it }

        var edgeCount = 0
        for (edge in graph.edgeList) {
            if (edgeCount == graph.vertices - 1)
                break

            val sourceParent = findParent(parent, edge.source)
            val destinationParent = findParent(parent, edge.destination)

            if (sourceParent != destinationParent) {
                result.add(edge)
                union(parent, sourceParent, destinationParent)
                edgeCount++
            }
        }

        return result
    }
}

class Edge:
    def __init__(self, source, destination, weight):
        self.source = source
        self.destination = destination
        self.weight = weight

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.edgeList = []

    def addEdge(self, source, destination, weight):
        self.edgeList.append(Edge(source, destination, weight))

class KruskalsAlgorithm:
    @staticmethod
    def findParent(parent, vertex):
        if parent[vertex] != vertex:
            parent[vertex] = KruskalsAlgorithm.findParent(parent, parent[vertex])
        return parent[vertex]

    @staticmethod
    def union(parent, x, y):
        rootX = KruskalsAlgorithm.findParent(parent, x)
        rootY = KruskalsAlgorithm.findParent(parent, y)
        parent[rootX] = rootY

    @staticmethod
    def kruskals(graph):
        result = []
        graph.edgeList.sort(key=lambda x: x.weight)

        parent = [i for i in range(graph.vertices)]

        edgeCount = 0
        for edge in graph.edgeList:
            if edgeCount == graph.vertices - 1:
                break

            sourceParent = KruskalsAlgorithm.findParent(parent, edge.source)
            destinationParent = KruskalsAlgorithm.findParent(parent, edge.destination)

            if sourceParent != destinationParent:
                result.append(edge)
                KruskalsAlgorithm.union(parent, sourceParent, destinationParent)
                edgeCount += 1

        return result

#[derive(Clone, Copy)]
struct Edge {
    source: usize,
    destination: usize,
    weight: i32,
}

struct Graph {
    vertices: usize,
    edge_list: Vec<Edge>,
}

impl Graph {
    fn new(vertices: usize) -> Self {
        Graph {
            vertices,
            edge_list: Vec::new(),
        }
    }

    fn add_edge(&mut self, source: usize, destination: usize, weight: i32) {
        self.edge_list.push(Edge {
            source,
            destination,
            weight,
        });
    }
}

fn find_parent(parent: &mut Vec<usize>, vertex: usize) -> usize {
    if parent[vertex] != vertex {
        parent[vertex] = find_parent(parent, parent[vertex]);
    }
    parent[vertex]
}

fn union(parent: &mut Vec<usize>, x: usize, y: usize) {
    let root_x = find_parent(parent, x);
    let root_y = find_parent(parent, y);
    parent[root_x] = root_y;
}

fn kruskals(graph: &Graph) -> Vec<Edge> {
    let mut result = Vec::new();
    let mut edge_list = graph.edge_list.clone();
    edge_list.sort_by_key(|x| x.weight);
    let mut parent: Vec<usize> = (0..graph.vertices).collect();

    let mut edge_count = 0;
    for edge in edge_list {
        if edge_count == graph.vertices - 1 {
            break;
        }
        let source_parent = find_parent(&mut parent, edge.source);
        let destination_parent = find_parent(&mut parent, edge.destination);
        if source_parent != destination_parent {
            result.push(edge);
            union(&mut parent, source_parent, destination_parent);
            edge_count += 1;
        }
    }
    result
}

class Edge {
  source: number;
  destination: number;
  weight: number;

  constructor(source: number, destination: number, weight: number) {
    this.source = source;
    this.destination = destination;
    this.weight = weight;
  }
}

class Graph {
  vertices: number;
  edgeList: Edge[];

  constructor(vertices: number) {
    this.vertices = vertices;
    this.edgeList = [];
  }

  addEdge(source: number, destination: number, weight: number) {
    this.edgeList.push(new Edge(source, destination, weight));
  }
}

class KruskalsAlgorithm {
  static findParent(parent: number[], vertex: number): number {
    if (parent[vertex] !== vertex) {
      parent[vertex] = this.findParent(parent, parent[vertex]);
    }
    return parent[vertex];
  }

  static union(parent: number[], x: number, y: number) {
    const rootX = this.findParent(parent, x);
    const rootY = this.findParent(parent, y);
    parent[rootX] = rootY;
  }

  static kruskals(graph: Graph): Edge[] {
    const result: Edge[] = [];
    graph.edgeList.sort((a, b) => a.weight - b.weight);

    const parent = Array.from({ length: graph.vertices }, (_, i) => i);

    let edgeCount = 0;
    for (const edge of graph.edgeList) {
      if (edgeCount === graph.vertices - 1) break;

      const sourceParent = this.findParent(parent, edge.source);
      const destinationParent = this.findParent(parent, edge.destination);

      if (sourceParent !== destinationParent) {
        result.push(edge);
        this.union(parent, sourceParent, destinationParent);
        edgeCount++;
      }
    }

    return result;
  }
}