Kruskal Algorithm In C

The algorithm evaluates every edge of the graph in increasing weight sequence and includes them in the minimum spanning tree if they do not create a cycle with the existing edges in the tree. Kruskal's method utilizes the disjoint-set data structure to avoid cycle formation.

Characteristics:

• ✅ If an edge does not form a cycle with edges already in the tree, the method evaluates all edges of the graph in ascending weight order and adds them to the minimal spanning tree.
• ✅ The algorithm maintains a set of disjoint subsets of vertices, with each subset representing a connected component of the graph. As edges are added to the selected set, the subsets are merged together, until all vertices belong to the same subset.

Usage:

Kruskal's algorithm finds applications in a range of scenarios, including network planning, clustering tasks, and image partitioning. It is commonly employed in engineering, computer science, and other fields requiring the analysis of graphs.

The Kruskal algorithm's steps are listed below:

• ✅ Sort all the edges according to weight in a non-decreasing order.
• ✅ Initialize an empty set for the minimum spanning tree and an empty disjoint-set data structure.
• ✅ Add the edge to the tree and combine the two sets that the edge's endpoints belong to in the disjoint-set data structure for each edge in the sorted order if doing so does not result in a cycle.
• ✅ Until all edges have been taken into account or the smallest spanning tree has n-1 edges-where n is the number of nodes in the graph-repeat step 3 as necessary.
• ✅ At the end of the algorithm, the minimum spanning tree will be the set of edges added to the tree in step 3. The temporal complexity of Kruskal's algorithm, where E is the number of edges and V is the number of vertices in the graph, is either O(ElogE) or O(ElogV).

Here is the code for Kruskal's algorithm written in the C programming language:

C Program:

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

#define MAX_EDGES 1000

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

typedef struct Graph {
    int V, E;
    Edge edges[MAX_EDGES];
} Graph;

typedef struct Subset {
    int parent, rank;
} Subset;

Graph* createGraph(int V, int E) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->V = V;
    graph->E = E;
    return graph;
}

int find(Subset subsets[], int i) {
    if (subsets[i].parent != i) {
        subsets[i].parent = find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
}

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++;
    }
}

int compare(const void* a, const void* b) {
    Edge* a_edge = (Edge*) a;
    Edge* b_edge = (Edge*) b;
    return a_edge->weight - b_edge->weight;
}

void kruskalMST(Graph* graph) {
    Edge mst[graph->V];
    int e = 0, i = 0;

    qsort(graph->edges, graph->E, sizeof(Edge), compare);

    Subset* subsets = (Subset*) malloc(graph->V * sizeof(Subset));
    for (int v = 0; v < graph->V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    while (e < graph->V - 1 && i < graph->E) {
        Edge next_edge = graph->edges[i++];

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

        if (x != y) {
            mst[e++] = next_edge;
            Union(subsets, x, y);
        }
    }

    printf("Minimum Spanning Tree:\n");
    for (i = 0; i < e; ++i) {
        printf("(%d, %d) -> %d\n", mst[i].src, mst[i].dest, mst[i].weight);
    }
}

int main() {
    int V, E;
    printf("Enter number of vertices and edges: ");
    scanf("%d %d", &V, &E);

    Graph* graph = createGraph(V, E);

    printf("Enter edges and their weights:\n");
    for (int i = 0; i < E; ++i) {
        scanf("%d %d %d", &graph->edges[i].src, &graph->edges[i].dest, &graph->edges[i].weight);
    }

    kruskalMST(graph);

    return 0;
}

This script prompts the user for the total vertices and edges of a graph, along with their corresponding weights. Subsequently, it executes Kruskal's algorithm on the graph and displays the resulting minimum spanning tree.

Kruskal's algorithm is utilized to find the minimum spanning tree in a connected, weighted graph. In the implementation of Kruskal's algorithm in C, the following steps are typically followed:

1. Sort all the edges in non-decreasing order of their weights.
2. Initialize an empty graph to store the minimum spanning tree.
3. Iterate through all the edges in sorted order and add the edge to the minimum spanning tree if it does not form a cycle.
4. Use a disjoint-set data structure to keep track of the connected components.

Below is an example of Kruskal's algorithm implementation in C:

// Function to implement Kruskal's algorithm
void kruskalMST() {
    // Sort all the edges in non-decreasing order of their weights
    
    // Initialize an empty graph to store the minimum spanning tree
    
    // Iterate through all the edges and add to the tree if no cycle is formed
    
    // Use disjoint-set data structure to keep track of connected components
}

int main() {
    // Call the function to implement Kruskal's algorithm
    
    return 0;
}

This implementation outlines the basic structure for applying Kruskal's algorithm in C to find the minimum spanning tree of a given graph.

Input:

Enter number of vertices and edges: 5 7
Enter edges and their weights:
0 1 2
0 3 6
1 2 3
1 3 8
1 4 5
2 4 7
3 4 9

Output:

Minimum Spanning Tree:
(0, 1) -> 2
(1, 2) -> 3
(1, 4) -> 5
(0, 3) -> 6

In this instance, the given scenario outlines a graph containing 5 vertices and 7 edges. Subsequently, the user provides input for the edge weights. The result of Kruskal's algorithm showcases the edges constituting the minimal spanning tree.

Advantages:

• ✅ Kruskal's algorithm is simple to implement and understand.
• ✅ It finds the minimum spanning tree of a graph in a reasonable amount of time, making it suitable for large graphs.
• ✅ The algorithm is suitable for a wide range of applications.

Disadvantages:

• ✅ The algorithm may not find the unique minimum spanning tree of a graph, since there may be multiple minimum spanning trees with the same total weight.
• ✅ The algorithm requires sorting the edges of the graph by weight, which can be time-consuming for large graphs.
• ✅ The algorithm requires extra space to store the disjoint subsets of vertices.

Conclusion:

The Kruskal algorithm is a simple yet efficient approach for finding the minimum spanning tree of a graph. In this context, E represents the total number of edges within the graph, and the algorithm's time complexity is O(E log E). This makes it particularly suitable for handling large-scale graphs.