Minimum Spanning Tree Using Kruskals Algorithm In C++

Introduction of the Kruskal's Algorithm:

In the rapidly evolving realm of technology and information, algorithms play a crucial role in tackling complex challenges. An intriguing algorithm known for its simplicity and efficiency is Kruskal's algorithm. Originating from graph theory, this algorithm excels in determining the most efficient way to establish connections within a graph.

Now, a "minimum spanning tree" may seem sophisticated, but it plays a crucial role in network design, architectural planning, and optimization problem-solving. It involves creating the most compact graph possible with the lowest combined edge weight. Kruskal's algorithm, attributed to the intelligent individual Joseph Kruskal, focuses on making optimal decisions at every stage to achieve the most efficient solution.

Exploring the functionality of Kruskal's algorithm involves understanding its fundamental concepts, implementation, and practical applications. Whether you have a passion for technology, are a student embarking on your learning journey, or a seasoned developer honing your skills, familiarizing yourself with Kruskal's algorithm enhances your comprehension of graphs and their significance in various contexts. Let's delve deeper into the intricacies of Kruskal's algorithm and appreciate its value in optimizing processes within graph theory.

Implementation in C++

Program:

Let's consider an illustration to apply Kruskal's algorithm for finding the minimum spanning tree in C++.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Define a structure to represent an edge
struct Edge {
 int src, dest, weight;
};

// Define a structure to represent a subset for union-find
struct Subset {
 int parent, rank;
};

// Compare function for sorting edges based on their weights
bool compareEdges(const Edge &a, const Edge &b) {
 return a.weight < b.weight;
}

// Find set of an element in union-find (with path compression)
int find(Subset subsets[], int i) {
 if (subsets[i].parent != i)
 subsets[i].parent = find(subsets, subsets[i].parent);
 return subsets[i].parent;
}

// Perform union of two subsets (by rank)
void Union(Subset subsets[], int x, int y) {
 int xroot = find(subsets, x);
 int yroot = find(subsets, y);

 if (subsets[xroot].rank < subsets[yroot].rank)
 subsets[xroot].parent = yroot;
 else if (subsets[xroot].rank > subsets[yroot].rank)
 subsets[yroot].parent = xroot;
 else {
 subsets[yroot].parent = xroot;
 subsets[xroot].rank++;
 }
}

// Kruskal's algorithm to find Minimum Spanning Tree
void Kruskal(vector<Edge> &edges, int V) {
 // Sort the edges in non-decreasing order of their weights
 sort(edges.begin(), edges.end(), compareEdges);

 // Allocate memory for creating V subsets
 Subset *subsets = new Subset[V];

 // Create V subsets with single elements
 for (int i = 0; i < V; ++i) {
 subsets[i].parent = i;
 subsets[i].rank = 0;
 }

 // Initialize result
 vector<Edge> result;

 // Number of edges to be taken is equal to V-1
 int edgeIndex = 0;
 while (result.size() < V - 1) {
 // Pick the smallest edge and increment the index for the next iteration
 Edge nextEdge = edges[edgeIndex++];

 int x = find(subsets, nextEdge.src);
 int y = find(subsets, nextEdge.dest);

 // If including this edge doesn't cause a cycle, add it to the result
 if (x != y) {
 result.push_back(nextEdge);
 Union(subsets, x, y);
 }
 }

 // Print the result
 for (const Edge &edge : result)
 cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;

 // Cleanup
 delete[] subsets;
}

int main() {
 // Example usage
 int V = 4; // Number of vertices
 vector<Edge> edges = {
 {0, 1, 10},
 {0, 2, 6},
 {0, 3, 5},
 {1, 3, 15},
 {2, 3, 4}
 };

 Kruskal(edges, V);

 return 0;
}

Output:

2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

Explanation:

1. Sort Edges by Weight:

Kruskal's algorithm starts by arranging all the graph edges in increasing order according to their weights. This step is crucial for the greedy approach utilized in the algorithm.

1. Set Up Subsets:

Form individual subsets for every vertex within the graph. Initially, each vertex is assigned to a unique subset.

1. Traverse Through Sorted Edges:

Commence with the shortest edge and proceed by iterating through the sorted edge list.

1. Verify for the presence of a cycle:

For every edge, verify if its inclusion in the expanding spanning tree would result in a cycle. This is achieved by confirming whether the edge's starting and ending vertices are part of different subsets. If they are not, then adding this edge will not lead to a cycle.

1. Merging Process:

If the addition of a new edge does not result in the formation of a cycle, it should be incorporated into the minimum spanning tree. The subsets need to be updated through the union operation, where the subsets of the source and destination vertices are merged together.

1. Continue this process iteratively until the spanning tree is fully constructed.

Continue this procedure until the minimum spanning tree contains V-1 edges, where V represents the total number of vertices. Once this threshold is reached, the spanning tree covers all vertices without creating any cycles.

1. Outcome:

The outcome is a minimal spanning tree that links all nodes by utilizing the smallest sum of edge weights.

Approach 2:

Let's consider a different scenario to apply Kruskal's algorithm for finding the minimum spanning tree in C++.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
 int src, dest, weight;
};

// Helper class for Union-Find with path compression
class UnionFind {
public:
 vector<int> parent, rank;

 UnionFind(int size) {
 parent.resize(size);
 rank.resize(size, 0);
 for (int i = 0; i < size; ++i) {
 parent[i] = i;
 }
 }

 int find(int x) {
 if (parent[x] != x) {
 parent[x] = find(parent[x]); // Path compression
 }
 return parent[x];
 }

 void unite(int x, int y) {
 int rootX = find(x);
 int rootY = find(y);

 if (rootX != rootY) {
 if (rank[rootX] < rank[rootY]) {
 parent[rootX] = rootY;
 } else if (rank[rootX] > rank[rootY]) {
 parent[rootY] = rootX;
 } else {
 parent[rootY] = rootX;
 rank[rootX]++;
 }
 }
 }
};

bool compareEdges(const Edge &a, const Edge &b) {
 return a.weight < b.weight;
}

void kruskalMST(vector<Edge> &edges, int V) {
 sort(edges.begin(), edges.end(), compareEdges);

 UnionFind uf(V);
 vector<Edge> result;

 for (const Edge &edge : edges) {
 int rootSrc = uf.find(edge.src);
 int rootDest = uf.find(edge.dest);

 if (rootSrc != rootDest) {
 result.push_back(edge);
 uf.unite(rootSrc, rootDest);
 }
 }

 for (const Edge &edge : result) {
 cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
 }
}

int main() {
 int V = 4;
 vector<Edge> edges = {
 {0, 1, 10},
 {0, 2, 6},
 {0, 3, 5},
 {1, 3, 15},
 {2, 3, 4}
 };

 kruskalMST(edges, V);

 return 0;
}

Output:

Minimum Spanning Tree:
Edge: 2 -- 3, Weight: 4
Edge: 0 -- 3, Weight: 5
Edge: 0 -- 1, Weight: 10

Explanation:

• ✅ Sorting Edges:

The algorithm commences by arranging all the edges in the graph according to their weights in ascending order.

It is commonly achieved through the implementation of a sorting algorithm, and the sorting phase plays a crucial role in Kruskal's algorithm.

• ✅ Disjoint-Set Data Structure:

Kruskal's algorithm leverages a data structure known as Union-Find to effectively identify cycles within the graph.

It maintains records of separate sets and enables rapid verification to determine if adding a new edge would result in a cycle.

• ✅ Choosing Edges:

Beginning from the tiniest edge, the procedure moves through the arranged edges in a sequential manner.

For every edge, it verifies whether including it in the expanding MST would result in a cycle by employing the Union-Find data structure.

• ✅ Incorporating Edges into MST:

If incorporating the edge does not result in a cycle, it will be included in the Minimum Spanning Tree (MST).

This procedure persists until the Minimum Spanning Tree (MST) comprises V-1 edges, with V representing the total vertices present in the graph.

Kruskal's Algorithm vs Prim's Algorithm:

Kruskal's Algorithm

• ✅ Strategy:

Greedy: Kruskal's algorithm operates with a greedy approach, where it picks the smallest edge currently accessible during every iteration.

• ✅ Edge Selection:

Independent of Vertices: It chooses edges regardless of the vertices they connect.

• ✅ Data Structures:

It commonly employs disjoint-set data structures to effectively detect cycles and execute union operations.

• ✅ Complexity:

Arranging edges based on their weights, a process known as edge sorting, can be a time-consuming task especially in graphs with a high density of edges.

• ✅ Applicability:

Sparse Graphs: It typically exhibits efficient performance with sparse graphs characterized by a much lower edge count compared to the maximum capacity.

• ✅ Concurrency:

More conducive to parallel processing because of the autonomous selection of edges.

Prim's Algorithm:

• ✅ Strategy:

Greedy: Similarly to Prim's algorithm, the greedy approach involves choosing the smallest edge that is currently accessible at every iteration.

• ✅ Edge Selection:

Dependent on an Initial Vertex: It picks edges according to a specified starting vertex and then expands the Minimum Spanning Tree (MST) from that initial point.

• ✅ Data Structures:

It commonly employs a priority queue to effectively choose the smallest edge connected to the expanding MST.

• ✅ Time Complexity:

Avoids Sorting: There is no need to sort all edges, which can lead to higher efficiency especially in graphs with a high density.

• ✅ Applicability:

It can operate efficiently on dense graphs because it doesn't need to sort all edges.

• ✅ Concurrency:

Limited Parallelization: Implementing parallelization becomes more complex because it relies on the initial vertex and necessitates the use of a priority queue.

Comparison Overview:

• ✅ Edge Sorting: Kruskal's involves sorting all edges, while Prim's doesn't require sorting. For dense graphs, Prim's may have an advantage in terms of time complexity.
• ✅ Parallelization: Kruskal's is often more parallelizable because the process of selecting edges is more independent. In contrast, Prim's can be more challenging to parallelize due to its dependency on a starting vertex.
• ✅ Space Complexity: Kruskal's typically has higher space complexity due to the use of disjoint-set data structures. Prim's may use less memory in certain scenarios.
• ✅ Starting Vertex: Kruskal's does not rely on a specific starting vertex, making it more straightforward to implement. Prim's requires selecting a starting vertex, which can influence the resulting MST.
• ✅ Applications: Both algorithms are used in various applications, such as network design, but the choice between them often depends on the specific characteristics of the graph and the problem requirements.

Advantages of Kruskal's Algorithm:

There are several advantages of the Kruskal's Algorithm . Some main advantages of the Kruskal's Algorithm are as follows:

• ✅ Simplicity: Kruskal's algorithm is relatively simple to understand and implement. Its straightforward logic and ease of implementation make it accessible for both learning and practical use.
• ✅ Greedy Approach: The algorithm follows a greedy approach by selecting the smallest edge at each step. This local optimization strategy leads to a globally optimal solution, ensuring that the overall minimum spanning tree is efficiently identified.
• ✅ Efficiency: Kruskal's algorithm is efficient, especially when implemented with data structures like disjoint-set data structures (union-find). These structures ensure quick checks for cycles and efficient subset union operations.
• ✅ Optimality: The algorithm guarantees the optimality of the solution. The minimum spanning tree produced by Kruskal's algorithm always has the smallest total edge weights, making it suitable for scenarios where minimizing the overall cost or weight is crucial.
• ✅ Distributed Computing: Kruskal's algorithm is suitable for distributed computing environments. The nature of its operations, particularly the ability to work with disconnected components, makes it applicable in scenarios where data and computation are distributed across multiple nodes.
• ✅ Versatility: Kruskal's algorithm is not limited to specific types of graphs. It can be applied to both dense and sparse graphs, making it versatile for a wide range of applications.
• ✅ No Initial Assumptions: Unlike some other algorithms, Kruskal's algorithm does not require any assumptions about the starting point. It starts with the smallest edge and builds the spanning tree incrementally, ensuring that the choice of a specific vertex as the starting point does not influence the solution.
• ✅ Parallelization: The algorithm's structure allows for parallelization, making it suitable for implementation in parallel computing environments. This feature can lead to improved performance in certain scenarios.

Kruskal's method is a robust technique for effectively addressing the minimum spanning tree issue in graphs, offering a blend of simplicity, optimality, and flexibility.

Applications of Kruskal's Algorithm:

There are several applications of Kruskal's Algorithm . Some main applications of the Kruskal's Algorithm are as follows:

• ✅ Network Design: Kruskal's algorithm is widely used in designing communication networks, such as computer networks, telecommunication networks, and transportation networks. It helps in establishing the most efficient connections between nodes to minimize costs or maximize data transfer rates.
• ✅ Circuit Design: In electronic circuit design, Kruskal's algorithm can be applied to minimize the total wire length while ensuring that all components are connected. It is particularly important in the design of integrated circuits and printed circuit boards.
• ✅ Urban Planning: Kruskal's algorithm can be utilized in urban planning to optimize the layout of roads, utilities, and infrastructure. It assists in creating a network that efficiently connects different parts of a city or region.
• ✅ Resource Management: In resource management and allocation, Kruskal's algorithm helps optimize the distribution of resources by identifying the most efficient pathways or connections. It can be applied in scenarios such as water distribution, energy transmission, or pipeline networks.
• ✅ Wireless Sensor Networks: In wireless sensor networks, where sensors need to be connected with the least amount of communication overhead, Kruskal's algorithm can be used to establish efficient communication links while minimizing overall energy consumption.
• ✅ Image Segmentation: In image processing, Kruskal's algorithm can be employed for image segmentation. It helps identify the most significant edges or connections in an image, contributing to tasks such as object recognition and computer vision.
• ✅ Robotics: In robotics, particularly in the path planning and coordination of robotic agents, Kruskal's algorithm can be used to determine the optimal paths for multiple robots to navigate through an environment.
• ✅ Biology and DNA Sequencing: In computational biology, Kruskal's algorithm can be applied to analyze biological data, such as the identification of evolutionary relationships among species or the sequencing of DNA fragments .
• ✅ VLSI Design (Very Large-Scale Integration): Kruskal's algorithm is useful in VLSI design for optimizing the layout of components on a chip. It helps minimize the total wire length, reducing delays and improving overall performance.
• ✅ Game Design: Kruskal's algorithm can be used in game development to create realistic terrain, road networks, or mazes. It assists in generating game environments that are both connected and efficient.

These software programs showcase the flexibility of Kruskal's algorithm in addressing optimization challenges concerning connectivity and efficient resource allocation in different fields.

Disadvantages of Kruskal's Algorithm:

There are several disadvantages of Kruskal's Algorithm . Some main disadvantages of the Kruskal's Algorithm are as follows:

• ✅ Inefficiency with Dense Graphs: Kruskal's algorithm can be inefficient when dealing with dense graphs where the number of edges is close to the maximum possible. This is because sorting a large number of edges can be time-consuming.
• ✅ Space Complexity: The algorithm's space complexity is relatively high, especially when using additional data structures like disjoint-set data structures. It can be a drawback in situations where memory usage is a concern.
• ✅ Doesn't Handle Disconnected Graphs Well: Kruskal's algorithm assumes that the given graph is connected. If the graph is not connected, additional steps or modifications are needed to handle disconnected components, making the implementation more complex.
• ✅ Not Suitable for Dynamic Graphs: The algorithm is designed for static graphs and does not naturally adapt to changes in the graph structure. If the graph is dynamic and edges are added or removed frequently, Kruskal's algorithm may not be the most efficient choice.
• ✅ Equal Weight Edges: If the graph contains edges with equal weights, Kruskal's algorithm may produce different minimum spanning trees for different implementations or sorting methods. This lack of uniqueness can be a disadvantage in certain scenarios.
• ✅ No Consideration for Edge Costs: Kruskal's algorithm only considers the weights of edges and does not take into account other factors, such as the cost of adding an edge. In some practical applications, the cost of adding an edge may not solely depend on its weight.
• ✅ May Not Be Optimal for Certain Cases: While Kruskal's algorithm guarantees the minimum spanning tree's optimality in terms of edge weights, it may not always produce the most optimal solution for specific real-world applications where other factors need consideration.
• ✅ Not Well-Suited for Parallelization: Although some parts of Kruskal's algorithm can be parallelized, the overall structure is not inherently well-suited for parallel processing. It can limit its performance in certain high-performance computing environments.

Even with these drawbacks, Kruskal's algorithm continues to be a robust and extensively applied approach for determining minimum spanning trees across different scenarios. Recognizing its constraints plays a vital role in selecting the most suitable algorithm for a particular issue or use case.

Conclusion:

In essence, Kruskal's algorithm, a prominent technique in the realm of graph theory, efficiently tackles the Minimum Spanning Tree (MST) problem through the adoption of a greedy approach. Its straightforwardness and efficiency arise from the arrangement of edges by weight and the utilization of the Union-Find data structure for identifying cycles. By systematically opting for the smallest non-cyclic edges, Kruskal's algorithm builds an MST that links all nodes with the least total edge weight. This adaptability allows its application in a range of fields like network layout, city development, and robotics. Despite its time complexity being affected by edge sorting, Kruskal's algorithm endures as a crucial instrument for enhancing connectivity in various contexts.