Kruskal's Algorithm in Graph

Welcome to our beginner's guide to Kruskal's Algorithm in Graph Theory! Kruskal's Algorithm is a fundamental method used to find the minimum spanning tree (MST) of a connected, undirected graph. Let's explore this important algorithm together!

Understanding the Problem Statement

Before delving into Kruskal's Algorithm, let's understand the problem it addresses. In graph theory, a spanning tree of an undirected graph is a subgraph that is a tree and connects all the vertices together without creating cycles.

The minimum spanning tree (MST) of a graph is the spanning tree with the smallest possible sum of edge weights. The goal of Kruskal's Algorithm is to find this minimum spanning tree efficiently.

What is Kruskal's Algorithm?

Kruskal's Algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph. It starts with an empty graph and adds the edges with the smallest weights while ensuring that no cycles are formed.

Kruskal's Algorithm is named after mathematician Joseph Kruskal, who first proposed it in 1956.

How does Kruskal's Algorithm Work?

Kruskal's Algorithm operates as follows:

  1. Sort all the edges of the graph in non-decreasing order of their weights.
  2. Initialize an empty graph to store the MST.
  3. Iterate through the sorted edges and add each edge to the MST if adding it does not create a cycle.
  4. Continue until all vertices are included in the MST or until the MST has (V - 1) edges, where V is the number of vertices in the graph.

Kruskal's Algorithm ensures that the MST remains acyclic and includes the edges with the smallest weights that connect all vertices together.

Kruskal's Algorithm Example

Let's explore Kruskal's Algorithm step by step to find the Minimum Spanning Tree (MST) of the following weighted graph:


        A---4---B
       /       /|
      2       5 |
     /       /  |
    C---3---D-1-E

Kruskal's Algorithm Steps:

  1. Start with an empty set to represent the MST.
  2. MST: {}
  3. Sort all edges in ascending order by their weights.
  4. Edges: [(D, E, 1), (A, C, 2), (C, D, 3), (A, B, 4), (B, D, 5)]
  5. Iterate through the sorted edges:
    • Choose the edge with the smallest weight (D - E).
    • MST: {(D, E, 1)}
    • Choose the next smallest edge (A - C).
    • MST: {(D, E, 1), (A, C, 2)}
    • Choose the next smallest edge (C - D).
    • MST: {(D, E, 1), (A, C, 2), (C, D, 3)}
    • Choose the next smallest edge (A - B).
    • MST: {(D, E, 1), (A, C, 2), (C, D, 3), (A, B, 4)}
    • Choose the next smallest edge (B - D).
    • MST: {(D, E, 1), (A, C, 2), (C, D, 3), (A, B, 4)}

The final Minimum Spanning Tree (MST) is represented by the set of edges:


        A---B
        |   |
        C---D---E

Kruskal's Algorithm selects the minimum-weight edges to create the MST while ensuring there are no cycles in the tree.

Example Application of Kruskal's Algorithm

Consider a scenario where you have a network of cities connected by roads, each road with a certain cost or distance. By applying Kruskal's Algorithm, you can determine the minimum cost to connect all cities with roads while ensuring that each city is reachable from any other city.

Implementing Kruskal's Algorithm in Code

Now, let's take a look at how we can implement Kruskal's Algorithm in code. We'll provide examples in several programming languages to help you get started:

The UnionFind data structure is used in Kruskal's algorithm to efficiently detect and avoid cycles while constructing the minimum spanning tree of a graph. Here is the link to read Union-Find: Union find Algo Tutorial


package codeKatha;

import java.util.*;

public class KruskalMST {

    public List<Edge> kruskalMST(Graph graph) {
    
        List<Edge> result = new ArrayList<>();
        
        UnionFind unionFind = new UnionFind(graph.size());
        
        PriorityQueue<Edge> minHeap = new PriorityQueue<>((a, b) -> a.weight - b.weight);
        
        for (Edge edge : graph.getAllEdges()) {
            minHeap.offer(edge);
        }
        
        while (!minHeap.isEmpty() && result.size() < graph.size() - 1) {
            Edge edge = minHeap.poll();
            int u = edge.source;
            int v = edge.destination;
            if (unionFind.find(u) != unionFind.find(v)) {
                unionFind.union(u, v);
                result.add(edge);
            }
        }
        
        return result;
    }
}

#include <iostream>
#include <vector>
#include <queue>
#include "Graph.h"
#include "UnionFind.h"

class KruskalMST {
public:
    std::vector<Edge> kruskalMST(Graph& graph) {
    
        std::vector<Edge> result;
        
        UnionFind unionFind(graph.size());
        
        std::priority_queue<Edge, std::vector<Edge>, CompareEdge> minHeap;

        for (Edge edge : graph.getAllEdges()) {
            minHeap.push(edge);
        }

        while (!minHeap.empty() && result.size() < graph.size() - 1) {
        
            Edge edge = minHeap.top();
            minHeap.pop();
            int u = edge.source;
            int v = edge.destination;

            if (unionFind.find(u) != unionFind.find(v)) {
                unionFind.unionSet(u, v);
                result.push_back(edge);
            }
        }

        return result;
    }
};

class KruskalMST:
    def kruskalMST(self, graph):
        result = []
        union_find = UnionFind(graph.size())
        min_heap = []

        for edge in graph.get_all_edges():
            heapq.heappush(min_heap, edge)

        while min_heap and len(result) < graph.size() - 1:
            edge = heapq.heappop(min_heap)
            u, v, weight = edge.source, edge.destination, edge.weight

            if union_find.find(u) != union_find.find(v):
                union_find.union(u, v)
                result.append(edge)

        return result

class KruskalMST {
    kruskalMST(graph) {
        const result = [];
        const unionFind = new UnionFind(graph.size());
        const minHeap = new PriorityQueue((a, b) => a.weight - b.weight);

        for (const edge of graph.getAllEdges()) {
            minHeap.offer(edge);
        }

        while (!minHeap.isEmpty() && result.length < graph.size() - 1) {
            const edge = minHeap.poll();
            const { source: u, destination: v } = edge;

            if (unionFind.find(u) !== unionFind.find(v)) {
                unionFind.union(u, v);
                result.push(edge);
            }
        }

        return result;
    }
}

Graph: Concept and Important Algorithms

1. Basics of Graph Data Structure
2. Breadth-First Search (BFS) in Graph
3. Depth-First Search (DFS) in Graph 
4. Topological Sort in Graph
5. Union-Find Algorithm in Graph
6. Prim's Algorithm in Graph 
7. Dijkstra's Algorithm in Graph
8. Kruskal's Algorithm in Graph

Congratulations! You've now learned the basics of Kruskal's Algorithm in graph theory. Feel free to experiment with the provided code examples and explore further applications of Kruskal's Algorithm in your projects.

Comments

Popular Posts on Code Katha

Java Interview Questions for 10 Years Experience

Spring Boot Interview Questions for 10 Years Experience

Sql Interview Questions for 10 Years Experience

Visual Studio Code setup for Java and Spring with GitHub Copilot

Spring Data JPA

Java interview questions - Must to know concepts

Data Structures & Algorithms Tutorial with Coding Interview Questions

Elasticsearch Java Spring Boot

Spring Boot Kafka Tutorial