Untitled
unknown
plain_text
a year ago
1.6 kB
3
Indexable
Never
#include <stdio.h> #include <stdbool.h> #define V 3 // Number of vertices in the graph // Function to find the vertex with the minimum key value int minKey(int key[], bool mstSet[]) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) { if (!mstSet[v] && key[v] < min) { min = key[v]; min_index = v; } } return min_index; } // Function to print the MST void printMST(int parent[], int graph[V][V]) { printf("Edge \tWeight\n"); for (int i = 1; i < V; i++) { printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]); } } // Function to implement Prim's algorithm void primMST(int graph[V][V]) { int parent[V]; // Array to store the MST int key[V]; // Key values used to pick minimum weight edge bool mstSet[V]; // To represent set of vertices included in MST for (int i = 0; i < V; i++) { key[i] = INT_MAX; mstSet[i] = false; } key[0] = 0; // Make the first vertex as the starting vertex parent[0] = -1; // First node is the root of the MST for (int count = 0; count < V - 1; count++) { int u = minKey(key, mstSet); mstSet[u] = true; for (int v = 0; v < V; v++) { if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) { parent[v] = u; key[v] = graph[u][v]; } } } printMST(parent, graph); } int main() { int graph[V][V] = { {0, 3, 9}, {3, 0, 2}, {9, 2, 0} }; primMST(graph); return 0; }