ADA Program - 1

1./* Program to find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal’s algorithm.*/

MANUAL PROGRAM \\\\

#include <stdio.h>
#include <stdlib.h>
const int MAXNODES = 10;
const int INF = 9999;

typedef struct {
    int u, v, cost;
} edge;

int FindParent(int v, int parent[]);
void Union_ij(int i, int j, int parent[]);
void InputGraph(int m, edge e[]);
int GetMinEdge(edge e[], int n);
void Kruskal(int n, edge e[], int m);

int main(int argc, char **argv) {
    int n = 6, m = 20;
    edge e[2*MAXNODES];
    printf("Enter the number of nodes and edges: ");
    scanf("%d %d", &n, &m);
    InputGraph(m, e);
    Kruskal(n, e, m);
    return 0;
}

void InputGraph(int m, edge e[]) {
    int i, u, v, cost;
    for(i=0; i<m; i++) { 
        printf("Enter edge and cost in the form u, v, w : \n");
        scanf("%d%d%d", &u, &v, &cost);
        e[i].u = u;
        e[i].v = v;
        e[i].cost = cost;
    }
}

void Kruskal(int n, edge e[], int m) {
    int i, j, count, k, sum, u, v, t[MAXNODES][2], pos;
    int parent[MAXNODES];
    count = 0;
    k = 0;
    sum = 0;
    for(i=0; i<n; i++) {
        parent[i] = i;
    }
    while(count != n-1) {
        pos = GetMinEdge(e, m);
        if(pos == -1) {
            break;
        }
        u = e[pos].u;
        v = e[pos].v;
        i = FindParent(u, parent);
        j = FindParent(v, parent);
        if(i != j) {
            t[k][0] = u;
            t[k][1] = v;
            k++;
            count++;
            sum += e[pos].cost;
            Union_ij(i, j, parent); 
        }
        e[pos].cost = INF;
    }
    if(count == n-1) {
        printf("\nSpanning tree exists");
        printf("\nThe Spanning tree is shown below\n");
        for(i=0; i<n-1; i++)
            printf("%d %d\n", t[i][0], t[i][1]);
        printf("\nCost of the spanning tree : %d\n", sum);
    }
    else
        printf("\nThe spanning tree does not exist\n");
}

int GetMinEdge(edge e[], int n) {
    int i, small, pos;
    small = INF;
    pos = -1;
    for(i=0; i<n; i++) {
        if(e[i].cost < small) {
            small = e[i].cost;
            pos = i;
        }
    }
    return pos;
}

int FindParent(int v, int parent[]) {
    while (parent[v] != v)
        v = parent[v];
    return v;
}

void Union_ij(int V1, int V2, int parent[]) {
    if(V1 < V2) 
        parent[V2] = V1;
    else
        parent[V1] = V2;
}

Enter the number of nodes and edges: 4 5
Enter edge and cost in the form u, v, w :
0 1 10
Enter edge and cost in the form u, v, w :
0 2 6
Enter edge and cost in the form u, v, w :
0 3 5
Enter edge and cost in the form u, v, w :
1 3 15
Enter edge and cost in the form u, v, w :
2 3 4

Spanning tree exists
The Spanning tree is shown below
2 3
0 3
0 1

Cost of the spanning tree : 19

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

#define MAXNODES 10
#define INF 9999

typedef struct {
    int u, v, cost;
} edge;

int FindParent(int v, int parent[]);
void Union_ij(int i, int j, int parent[]);
void InputGraph(int m, edge e[]);
int GetMinEdge(edge e[], int n);
void Kruskal(int n, edge e[], int m);

int main(int argc, char **argv) {
    int n = 6, m = 20;
    edge e[2*MAXNODES];
    printf("Enter the number of nodes and edges: ");
    scanf("%d %d", &n, &m);
    InputGraph(m, e);
    Kruskal(n, e, m);
    return 0;
}

void InputGraph(int m, edge e[]) {
    int i, u, v, cost;
    for(i=0; i<m; i++) {
        printf("Enter edge and cost in the form u, v, w : \n");
        scanf("%d%d%d", &u, &v, &cost);
        e[i].u = u;
        e[i].v = v;
        e[i].cost = cost;
    }
}

void Kruskal(int n, edge e[], int m) {
    int i, j, count, k, sum, u, v, t[MAXNODES][2], pos;
    int parent[MAXNODES];
    count = 0;
    k = 0;
    sum = 0;
    
    for(i=0; i<n; i++) {
        parent[i] = i;
    }
    
    while(count != n-1) {
        pos = GetMinEdge(e,m);
        if(pos == -1)
            break;
        
        u = e[pos].u;
        v = e[pos].v;
        i = FindParent(u,parent);
        j = FindParent(v,parent);
        
        if(i != j) {
            t[k][0] = u;
            t[k][1] = v;
            k++;
            count++;
            sum += e[pos].cost;
            Union_ij(i, j, parent);
        }
        e[pos].cost = INF;
    }
    
    if(count == n-1) {
        printf("\nSpanning tree exists");
        printf("\nThe Spanning tree is shown below\n");
        for(i=0; i<n-1; i++)
            printf("%d %d\n",t[i][0], t[i][1]);
        printf("\nCost of the spanning tree : %d\n", sum);
    } else {
        printf("\nThe spanning tree does not exist\n");
    }
}

int GetMinEdge(edge e[], int n) {
    int i, small, pos;
    small = INF;
    pos = -1;
    for(i=0; i<n; i++) {
        if(e[i].cost < small) {
            small = e[i].cost;
            pos = i;
        }
    }
    return pos;
}

int FindParent(int v, int parent[]) {
    while (parent[v] != v)
        v = parent[v];
    return v;
}

void Union_ij(int V1, int V2, int parent[]) {
    if(V1 < V2)
        parent[V2] = V1;
    else
        parent[V1] = V2;
}
OUTPUT:
Enter the number of nodes and edges: 3 3
Enter edge and cost in the form u, v, w :
0 1 1
Enter edge and cost in the form u, v, w :
1 2 2
Enter edge and cost in the form u, v, w :
0 2 3

Spanning tree exists
The Spanning tree is shown below
0 1
1 2

Cost of the spanning tree : 3