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: {}
  2. Sort all edges in ascending order by their weights.
    3. Edges: [(D, E, 1), (A, C, 2), (C, D, 3), (A, B, 4), (B, D, 5)]
  3. 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.

Related categories:

Comments

Post a Comment

Popular Posts on Code Katha

Java Interview Questions for 10 Years Experience

Image
Welcome to the comprehensive guide on "Java Interview Questions for 10 Years Experience." Java has been one of the most popular programming languages for decades, and its widespread adoption means that the demand for skilled Java developers has never been higher. If you are someone who has been working with Java for the last decade, you have accumulated a wealth of experience and knowledge that you can showcase during interviews. Recommended  to read and brush up for your interview: Must know interview questions and concept for any Java Interview Spring boot interview Questions for 10 years experiance This blog post will provide you with a list of commonly asked interview questions for 10 years experienced Java developers. It will also include detailed answers to each question, with explanations and examples to help you understand the concepts and their practical implementations better. Whether you are preparing for a job interview or just want to brush up your knowl
Read more

Sql Interview Questions for 10 Years Experience

Image
As an experienced SQL professional, you might encounter challenging questions during a job interview. In this blog post, we will explore 10 common SQL interview questions and provide in-depth explanations along with relevant examples. Let's dive in! Contents [ hide ] What is SQL Injection, and how can you prevent it? SQL Injection is a malicious attack where an attacker manipulates input data to execute unintended SQL statements. It can lead to unauthorized access, data breaches, and data manipulation. To prevent SQL Injection, follow these best practices: 1.1. Use Prepared Statements: Prepared statements or parameterized queries separate SQL code from data input, preventing attackers from injecting malicious SQL code. Here's an example in PHP: $stmt = $pdo->prepare('SELECT * FROM users WHERE username = :username'); $stmt->bindParam(':username', $username); $stmt->execute(); 1.2. Sanitize User Input: Validate and sanitize user input
Read more

Spring Boot Interview Questions for 10 Years Experience

Image
Welcome to the comprehensive guide on "Spring Boot Interview Questions for 10 Years Experience". Spring Boot has become one of the most popular frameworks for developing enterprise-grade applications, and its widespread adoption means that the demand for skilled Spring Boot developers has never been higher. If you are someone who has been working with Spring Boot for the last decade, you have accumulated a wealth of experience and knowledge that you can showcase during interviews. Recommended  to read and brush up for your interview: Must know interview questions and concept for any Java Interview Java Interview Questions for 10 Years Experience This blog post will provide you with a list of commonly asked interview questions for 10 years experienced Spring Boot developers. It will also include detailed answers to each question, with explanations and examples to help you understand the concepts and th
Read more

Visual Studio Code setup for Java and Spring with GitHub Copilot

Image
Introduction- In this tutorial blog, we will explore the process of setting up and utilising Visual Studio Code for Java programming, as well as incorporating GitHub Copilot as a valuable coding tool. Visual Studio Code is a powerful and versatile code editor that offers a wide range of features and extensions for Java developers. By using Visual Studio Code for Java programming, developers can benefit from features such as code completion, debugging, and live coding. Additionally, with the integration of GitHub Copilot, developers can streamline their coding process with AI-assisted suggestions for code snippets and functions. This blog will provide a comprehensive guide for setting up and using these tools for Java development. Contents [ hide ] Setup Visual Studio Code for Java and Spring Visual Studio Code (VS Code) is an open-source code editor that supports a wide range of programming languages, including Java. It is a powerful tool
Read more

Java interview questions - Must to know concepts

Contents [ hide ] How does Java achieve platform independence, and what is the underlying principle? Java programs can run on diverse operating systems and hardware setups without requiring modification. This feat is primarily achieved through the concept of the Java Virtual Machine (JVM). The Java Virtual Machine (JVM) The JVM acts as a bridge between the Java code you write and the underlying hardware and operating system . When you compile your Java code, it is translated into an intermediate form called bytecode, which is not tied to any specific platform. The JVM then comes into play. It takes this bytecode and dynamically translates it into machine-specific instructions that the host system can execute. This means that a Java program can be written once and executed on any system with the appropriate JVM for that system. Example: Running a Java Program on Different Platforms Consider a simple Java program that calculates the sum of two numbers: package codeKatha
Read more

Spring Data JPA

Image
Introduction- We will learn here Spring Data JPA, perform CRUD operation, Clear concept of Relationship mapping like one-to-many, many-to-one with Example. Spring Data JPA is a powerful framework that simplifies the process of working with relational databases in Java applications. It provides an easy-to-use API for working with JPA, allowing developers to focus on their business logic instead of worrying about the details of how JPA works. With Spring Data JPA, you can easily define entities that map to database tables, and then use them to perform CRUD (create, read, update, delete) operations on those tables. In addition, Spring Data JPA provides support for more advanced features like querying and pagination, making it an excellent choice for both small and large projects. Contents [ hide ] In this blog, we will explore Spring Data JPA by building a sample application that uses it to manage users and packs. But, before let
Read more

Data Structures & Algorithms Tutorial with Coding Interview Questions

Image
About the Course This course offers comprehensive coverage of coding questions that serve as a solid foundation for understanding DSA concepts. These questions are frequently asked in coding interviews, either directly or with some variations, by many companies, including Adobe, Facebook (Meta), Paytm, Amazon, Google, and others. Our primary objective is to enhance your problem-solving skills and enable you to devise optimal solutions. The course includes a wide range of topics, such as Arrays, Strings, Searching and Sorting, Greedy Algorithms, Trees, Graphs, Dynamic Programming, and more. Upon completion, you will possess the necessary skills to ace DSA interviews for typical companies or excel in the initial rounds of product-based companies such as Google, Microsoft and similar others. We are started with Graph data Structure and add others soon. Contents [ hide ] Approach Our course is  organised into chapters that foll
Read more

Elasticsearch Java Spring Boot

Image
Introduction- In this blog, we will learned how to use Elasticsearch with Spring Boot to build a search application. We will created several classes as an example, including ElasticsearchConfig, Book, BookService, BookController, and BookRepository, to demonstrate how to use Elasticsearch with Spring Boot. After this tutorial, you can start building your own search application using Elasticsearch and Spring Boot. Elasticsearch is a powerful search and analytics engine that can be used to build highly scalable and fault-tolerant applications. In this blog, we will learn how to use Elasticsearch with Spring Boot to build a search application. First we will Set up a Spring Boot project with Elasticsearch after that we will see how to make connection with elasticsearch. Once connection setupt is done then we will add data then perform queries and searching on Elasticsearch. Contents [ hide ] Setting up a Spring Boot project with Elas
Read more

Java interview questions for 5 years experience

Contents [ hide ] What is difference between Heap and Stack Memory in Java, and shed light on their utilization? In Java, memory management plays a crucial role in determining how objects are stored and accessed during program execution . Heap and Stack Memory are two distinct regions where different types of data are managed. Understanding their differences is essential for efficient memory utilisation and managing object lifecycles. Stack Memory Stack Memory is a region used for storing method calls, local variables, and references to objects . It operates in a Last-In-First-Out (LIFO) manner , resembling a stack of items. Each method call creates a new frame in the stack, containing variables specific to that method. Stack Memory is relatively fast for allocation and deallocation because it follows a strict order. However, it has limited space and is typically used for small, short-lived data. Primitive data types and references to objects are often stored here. Ex
Read more