Kruskal's Algorithm

Kruskal's Algorithm finds a minimum spanning tree of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree(MST).
It is a greedy algorithm in graph theory as in each step it adds the next lowest-weight edge that will not form a cycle to the minimum spanning tree.

Lets Code :D

But first lets read the step wise guide :)

What we need?

1. Class Edge :- Properties : i) Source ii) Destination iii) Weights
2. Array of type Edge of size e (number of edges) - Input from user
3. Array output of type Edge of size e - 1 (the required MST)

STEPS:

1. Take input.
2. Sort the input array in increasing order according to their weights.
3. Create a parent array of size n (number of vertices) as - parent[n] = { 0, 1, 2, 3, ...}
4. Initialize count as 0.
5. while ( count < n - 1){ e edge is between two vertices - v1 and v2 parent of v1 is let, v1P and parent of v2 is let, v2p. If parent is same, next iteration. Else count + 1, update parent[] }
6. At last you'll get minimum spanning tree and then print the output.

Easy?

Below is the code for Kruskal's Algorithm in C++

Hope you enjoyed :)

Comments

[ZigRazor]

Great Job,

I'm doing a large work to create a comprehensive header-only library for C++ for graph Representation, Manipulation, Partitioning and Algorithms.

I'm looking for Contributor, but also a simple feedback is good enough.
If you have 5 min to check my repo I'd be very grateful.

ZigRazor / CXXGraph

Header-Only C++ Library for Graph Representation and Algorithms

CXXGraph

Table of Contents

• CXXGraph
  • Table of Contents
  • Introduction
  • Algorithm Explanation
    • Dijkstra
    • Dial
    • BFS
    • DFS
    • Cycle Detection
  • Partition Algorithm Explanation
    • Vertex-Cut
      • Greedy Vertex-Cut
  • Classes Explanation
  • Requirements
  • How to use
  • Unit-Test Execution
    • How to Compile
    • How to Run
  • Example
  • How to contribute
  • Site
  • Contact
  • Support
  • References
  • Credits
  • We are Looking for...

Introduction

CXXGraph is a small library, header only, that manages the Graph and it's algorithms in C++. In other words a "Comprehensive C++ Graph Library".

Algorithm Explanation

Dijkstra

Graph Dijkstras Shortest Path Algorithm(Dijkstra's Shortest Path) Dijkstra's Algorithm is used to find the shortest path from a source node to all other reachable nodes in the graph. The algorithm initially assumes all the nodes are unreachable from the given source node so we mark the distances of all nodes as infinity (infinity) from source node (INF / infinity denotes unable to reach).

Dial

Dial specialization of dijkstra’s algorithm.

When edge…

View on GitHub

Thank you so much in advance.
Best regards