Overview

The provided code is a C program that implements Prim's algorithm to find the Minimum Spanning Tree (MST) of a weighted undirected graph. The program utilizes a cost matrix to represent graph weights and constructs the MST based on the minimum edges.

Code Snippet

The code is written in C:

#include

int parent[10], min, ne=1, mincost=0;
int i, j, a, b, u, v, n;

int main() {
    printf("Enter the no. of vertices:\n");
    n = 6;
    printf("Enter the graph data:\n");
    
    int cost[6][6] = {
        {999, 3, 999, 999, 6, 5}, 
        {3, 999, 1, 999, 999, 4}, 
        {999, 1, 999, 6, 999, 4}, 
        {999, 999, 6, 999, 8, 5}, 
        {6, 999, 999, 8, 999, 2}, 
        {5, 4, 4, 5, 2, 999}
    };
    
    while (ne < n) {
        for (i = 0, min = 999; i < n; i++) 
            for (j = 0; j < n; j++) 
                if (cost[i][j] < min) {           
                    min = cost[i][j]; 
                    a = u = i; 
                    b = v = j; 
                }
        
        while (parent[u])
            u = parent[u]; 
        while (parent[v])
            v = parent[v];

        if (u != v) { 
            printf("\n%d\tEdge\t(%d,%d)=%d", ne++, a + 1, b + 1, min); 
            mincost += min; 
            parent[v] = u;
        }
        cost[a][b] = cost[b][a] = 999; 
    }

    printf("\n\tMINCOST=%d\n", mincost);
    return 1;
}

Code Relations Visualization

Below is a representation of the code's structure and relations using DOT notation:

digraph G {
    main [label="main()"];
    vertice [label="Variables: parent[], min, ne, mincost, i, j, a, b, u, v, n"];
    graph_data [label="Graph Data: cost[6][6]"];
    loop1 [label="While Loop: (ne < n)"];
    loop2 [label="Two Nested For Loops"];
    condition1 [label="If Condition: (cost[i][j] < min)"];
    update1 [label="Update min, a, u, b, v"];
    loop3 [label="While Loop: (parent[u])"];
    loop4 [label="While Loop: (parent[v])"];
    condition2 [label="If Condition: (u != v)"];
    output1 [label="Output Edge and Update mincost"];
    update2 [label="Update parent[v]"];
    update3 [label="Reset cost[a][b] to 999"];
    output2 [label="Output MINCOST"];

    main -> vertice;
    main -> graph_data;
    main -> loop1;
    loop1 -> loop2;
    loop2 -> condition1;
    condition1 -> update1;
    loop1 -> loop3;
    loop1 -> loop4;
    loop3 -> condition2;
    loop4 -> condition2;
    condition2 -> output1;
    condition2 -> update2;
    loop1 -> update3;
    main -> output2;
}

Key Points

• Purpose: The code implements Prim's Minimum Spanning Tree algorithm.
• Input: The number of vertices and the cost matrix representing the graph.
• Output: The edges chosen for the MST and the total minimum cost.
• Structure: Utilizes loops for iterating through vertices and conditions for checking minimum costs.

For further learning on similar topics, consider exploring the resources offered by the Enterprise DNA Platform.