Scribd
Upload
20 views2 pages

Prims Algorithm

The document contains a C program that implements Prim's algorithm to find the Minimum Spanning Tree (MST) of a graph represented by an adjacency matrix. It defines functions to find the minimum weight edge and to construct the MST, outputting the connections and weights of the vertices. The graph consists of four vertices, with specific weights between them defined in the adjacency matrix.

Uploaded by

maariaam.gh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
20 views2 pages

Prims Algorithm

The document contains a C program that implements Prim's algorithm to find the Minimum Spanning Tree (MST) of a graph represented by an adjacency matrix. It defines functions to find the minimum weight edge and to construct the MST, outputting the connections and weights of the vertices. The graph consists of four vertices, with specific weights between them defined in the adjacency matrix.

Uploaded by

maariaam.gh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

#include <stdio.

h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define N 4 // Number of vertices in the graph

// Function to find the vertex with the minimum weight


// among those not yet included in the MST
int minRoad(int road[], bool mst[]) {
int min = INT_MAX;
int min_index = -1;

for (int i = 0; i < N; ++i) {


if (road[i] < min && !mst[i]) {
min = road[i];
min_index = i;
}
}
return min_index;
}

// Prim's algorithm for building a Minimum Spanning Tree (MST)


void prim(int g[][N]) {
int parent[N]; // Stores the parent of each vertex
bool mst[N] = {false}; // Marks whether the vertex is included in the MST
int road[N]; // Minimum distance to the MST

// Initialize all distances to infinity


for (int i = 0; i < N; ++i)
road[i] = INT_MAX;

road[0] = 0; // Start from vertex 0


parent[0] = -1; // The root of the tree has no parent

for (int i = 0; i < N - 1; ++i) {


int index = minRoad(road, mst); // Select the vertex with the minimum edge
mst[index] = true; // Include it in the MST

for (int j = 0; j < N; ++j) {


if (g[index][j] && !mst[j] && g[index][j] < road[j]) {
parent[j] = index;
road[j] = g[index][j];
}
}
}

// Output the result


for (int i = 1; i < N; ++i) {
printf("Vertex %c is connected to vertex %c, weight: %d\n",
'A' + parent[i], 'A' + i, g[i][parent[i]]);
}
}
int main() {
// Adjacency matrix of the graph: A–B–C–D
int g[][N] = {
{0, 4, 5, 0},
{4, 0, 7, 6},
{5, 7, 0, 5},
{0, 6, 5, 0}
};

prim(g); // Run the algorithm


}

You might also like