Mastering Efficiency: A Deep Dive into the Kruskal Algorithm in Data Structures

Introduction

Kruskal's algorithm presents the idea in the graph theory of discrete mathematics. In linked weighted graphs, it employs to find the shortest path between two points. This algorithm treats each node as a separate tree and turns a given graph into a forest. Only when an edge between two trees has a low value and doesn't cause a cycle in the minimum spanning tree (MST) structure can the trees link to one another. Let’s explore more about the Kruskal Algorithm in data structure and its applications.

Overview

As was previously noted, the Kruskal algorithm produces the least spanning tree of a given graph. However, what is a minimal spanning tree exactly? The minimum spanning tree is a subset of a graph with edges equal to the number of vertices minus one and the same number of vertices as the graph. Additionally, it has a low cost for the whole of a spanning tree's edge weights.

The Kruskal algorithm adds nodes to the tree only in cases when the selected edge does not form a cycle, and it sorts all of the edges in ascending order of their edge weights. Furthermore, it selects the edge with the lowest cost initially and the highest cost last. To discover the global optimal solution, the Kruskal algorithm in data structure therefore makes a locally optimal decision. For this reason, we know it as a greedy algorithm.

Before diving straight into the algorithm, let's review some basic terminologies like minimum spanning tree and spanning tree.

1. A Spanning Tree: The subgraph of an undirected connected graph is called a spanning tree.

2. Minimum Spanning Tree: A minimum spanning tree is one in which all of the edge weights added together equal a minimum value. The total weight applied to the spanning tree's edges equals the weight of the spanning tree.
   

How is the Kruskal Algorithm Implemented?

When using Kruskal's algorithm, we begin with the edges that have the lowest weight and continue adding edges until we achieve the desired result. The following is a list of stages to implement Kruskal's algorithm:

• Sort every edge first, going from lightest to heaviest weight.
• The edge with the least weight should now be included in the spanning tree. Should the proposed edge result in a cycle, it should be rejected.
• Once all vertices are reached, add more edges until a minimal spanning tree is formed.

The following are some uses for Kruskal's algorithm:

• Wiring between cities can be laid out using Kruskal's algorithm.
• It has the ability to establish LAN connections.
  

A Kruskal Algorithm Example

Let's now use an example to demonstrate how Kruskal's method operates. The following Kruskal algorithm for minimum spanning tree example will make Kruskal's algorithm easier to understand.

Assume that a graph with weights is:

The table below pro

vides the edge weights of the graph above:

Next, sort the aforementioned edges according to increasing weights.

Let's begin building the least spanning tree now.

Step 1: To begin, add to the MST the edge AB with weight 1.

Step 2: Since the edge DE isn't starting the cycle, add it to the MST along with weight 2.

Step 3: Since the edge BC with weight 3 isn't producing a cycle or loop, add it to the MST.

Step 4: Since the edge CD isn't generating the cycle, pick it now and weigh it down to the MST.

Step 5: Select the edge AE with weight 5 after that. This edge should be discarded since including it will start the loop.

Step 6: Select the edge AC with weight 7. This edge should be discarded since including it will start the loop.

Step 7: Choose the edge AD with weight 10. Discard this edge because including it will also start the cycle.

Thus, using Kruskal's approach, the final least spanning tree that is generated from the provided weighted graph is,

Therefore, the MST cost is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

The number of vertices in the tree above less one is now equal to the number of edges. So the algorithm ends here.

The Algorithm:

Step 1: Construct a forest F such that each graph vertex represents a separate tree.

Step 2: Create a set E consisting of every edge in the graph.

Step 3: While E is NOT EMPTY and F is not spanning, repeat Steps 4 and 5.

Step 4: With the least amount of weight, remove an edge from E.

Step 5: Add the edge to the forest F (for integrating two trees into one tree) if the edge obtained in Step 4 joins two different trees.

ELSE

Throw away the edge.

Step 6: END.

The Kruskal's Algorithm Complexity

Let us now examine the algorithm's time complexity, Kruskal's. The time complexity of Kruskal's algorithm can be broken down as follows:

• Worst-case time Complexity: The worst-case time complexity of Kruskal's algorithm is typically O(E log E). Here, E indicates the number of edges in the graph. This complexity arises from the sorting of edges based on weight.

• Average Case Time Complexity: The average-case time complexity of Kruskal's algorithm is also O(E log E), as it primarily depends on the sorting of edges.

• Best Case Time Complexity: The best-case time complexity of Kruskal's algorithm is also O(E log E). Even if the graph is disconnected or has fewer edges, the sorting operation still dominates the time complexity.

Application of the Kruskal Algorithm

Let's now examine how Kruskal's algorithm is put into practice.

1. Kruskal Algorithm c++

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1e4 + 5;
int id[MAX], nodes, edges;
pair <long long, pair<int, int> > p[MAX];
void init()
{
for(int i = 0;i < MAX;++i)
id[i] = i;
}
int root(int x)
{
while(id[x] != x)
{
id[x] = id[id[x]];
x = id[x];
}
return x;
}
void union1(int x, int y)
{
int p = root(x);
int q = root(y);
id[p] = id[q];
}
long long kruskal(pair<long long, pair<int, int> > p[])
{
int x, y;
long long cost, minimumCost = 0;
for(int i = 0;i < edges;++i)
{
x = p[i].second.first;
y = p[i].second.second;
cost = p[i].first;
if(root(x) != root(y))
{
minimumCost += cost;
union1(x, y);
}
}
return minimumCost;
}
int main()
{
int x, y;
long long weight, cost, minimumCost;
init();
cout <<"Enter Nodes and edges";
cin >> nodes >> edges;
for(int i = 0;i < edges;++i)
{
cout<<"Enter the value of X, Y and edges";
cin >> x >> y >> weight;
p[i] = make_pair(weight, make_pair(x, y));
}
sort(p, p + edges);
minimumCost = kruskal(p);
cout <<"Minimum cost is "<< minimumCost << endl;
return 0;
}

Output:

Enter Nodes and edges 5 7
Enter the value of X, Y and edges 1 2 1
Enter the value of X, Y and edges 1 3 7
Enter the value of X, Y and edges 1 4 10
Enter the value of X, Y and edges 1 5 5
Enter the value of X, Y and edges 2 3 3
Enter the value of X, Y and edges 3 4 4
Enter the value of X, Y and edges 4 5 2
Minimum cost is 10

2. A C Program for Kruskal's Algorithm

#include <stdio.h>
#include <stdlib.h>

// Structure to represent an edge in the graph
struct Edge {
int src, dest, weight;
};

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

// Function prototypes
int find(struct Subset subsets[], int i);
void Union(struct Subset subsets[], int x, int y);
int compareEdges(const void* a, const void* b);
void KruskalMST(struct Edge edges[], int V, int E);

// Main function
int main() {
int V = 4; // Number of vertices in the graph
int E = 5; // Number of edges in the graph

struct Edge edges[] = {
{0, 1, 10},
{0, 2, 6},
{0, 3, 5},
{1, 3, 15},
{2, 3, 4}
};

KruskalMST(edges, V, E);

return 0;
}

// Find set of an element i (uses path compression technique)
int find(struct 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 sets x and y (uses union by rank)
void Union(struct 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++;
}
}

// Compare two edges based on their weights
int compareEdges(const void* a, const void* b) {
struct Edge* edge1 = (struct Edge*)a;
struct Edge* edge2 = (struct Edge*)b;
return edge1->weight - edge2->weight;
}

// Function to construct MST using Kruskal's algorithm
void KruskalMST(struct Edge edges[], int V, int E) {
struct Edge result[V]; // Array to store the resultant MST
int e = 0; // Index variable for result[]
int i = 0; // Index variable for sorted edges

// Step 1: Sort all the edges in non-decreasing order of their weight
qsort(edges, E, sizeof(edges[0]), compareEdges);

// Allocate memory for creating V subsets
struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));

// Initialize each subset
for (int v = 0; v < V; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}

// Number of edges to be taken is equal to V-1
while (e < V - 1 && i < E) {
// Step 2: Pick the smallest edge, and increment the index for next iteration
struct Edge next_edge = edges[i++];

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

// If including this edge doesn't cause a cycle, include it in result and increment the index of result for next edge
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
}

// Print the constructed MST
printf("Edges of the constructed MST:\n");
for (i = 0; i < e; ++i)
printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);

// Free allocated memory
free(subsets);
}

Output:

Edges of the constructed MST:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

Conclusion

Within data structures, the Kruskal algorithm has provided a perfect implementation for finding minimal spanning trees through an edge-based selection process and a union-find operation with conditions of no cycle tolerance. For this simplicity and high performance in processing bigger datasets, it is a building block in graph algorithms.

FAQs

1. What is Kruskal's algorithm program in data structure?

Kruskal's algorithm is a method used to find the minimum spanning tree of a connected, weighted graph. It operates by selecting edges in ascending order of weight and adding them to the spanning tree, avoiding cycles.

2. What is Kruskal and Prim's algorithm?

Kruskal's and Prim's algorithms are both used to find minimum spanning trees in graphs. Kruskal's algorithm operates by selecting edges in ascending order of weight and adding them to the spanning tree, while Prim's algorithm starts with a single vertex and grows the spanning tree from there, selecting the shortest edge at each step.

3. What is Kruskal's algorithm array?

In Kruskal's algorithm, an array is used to store the edges of the graph. These edges are sorted in a non-decreasing order of weight, allowing the algorithm to efficiently select the next edge to add to the minimum spanning tree.

4. What are the conditions for Kruskal's algorithm?

Kruskal's algorithm requires the graph to be connected and weighted. It can handle both undirected and directed graphs, but it's commonly used with undirected graphs. Additionally, the graph should not contain any negative-weight edges.

5. What is Kruskal's importance algorithm?

Kruskal's algorithm is important for finding minimum spanning trees in graphs, which has numerous applications in various fields such as network design, circuit wiring, and transportation planning. It offers an efficient and straightforward approach to optimizing connectivity while minimizing cost.

6. What are the advantages of Kruskal's algorithm?

Kruskal's algorithm is advantageous due to its simplicity of implementation, efficiency in handling large datasets, and its ability to find the minimum spanning tree of a graph with relatively low computational complexity.