Scribd
Upload
4 views4 pages

Prim's Algorithm Implementation in C

The document contains a C++ implementation of a graph class that supports adding edges and finding the minimum spanning tree (MST) using Prim's algorithm. It includes methods for managing nodes and edges, as well as a main function that prompts the user to input edges and weights. The program outputs the edges of the MST and its total weight.

Uploaded by

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

Prim's Algorithm Implementation in C

The document contains a C++ implementation of a graph class that supports adding edges and finding the minimum spanning tree (MST) using Prim's algorithm. It includes methods for managing nodes and edges, as well as a main function that prompts the user to input edges and weights. The program outputs the edges of the MST and its total weight.

Uploaded by

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

#include <iostream>

#include <unordered_map>
#include <vector>
#include <climits>
using namespace std;

class Graph {
int n;
int adj[100][100];
unordered_map<string, int> nodeToIndex;
vector<string> indexToNode;
int nodeCount = 0;

public:
Graph(int nodes) {
n = nodes;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
adj[i][j] = 0;
}
}
}

void addEdge(string uName, string vName, int w) {


int u = getNodeIndex(uName);
int v = getNodeIndex(vName);
adj[u][v] = w;
adj[v][u] = w; // undirected graph
}

int getNodeIndex(string nodeName) {


if ([Link](nodeName) == [Link]()) {
nodeToIndex[nodeName] = nodeCount;
indexToNode.push_back(nodeName);
nodeCount++;
}
return nodeToIndex[nodeName];
}

int findMinKey(int key[], bool visited[]) {


int min = INT_MAX, minIndex = -1;
for (int i = 0; i < nodeCount; i++) {
if (!visited[i] && key[i] < min) {
min = key[i];
minIndex = i;
}
}
return minIndex;
}

void primMST() {
int parent[100];
int key[100];
bool visited[100];
int totalWeight = 0;

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


key[i] = INT_MAX;
visited[i] = false;
}

key[0] = 0;
parent[0] = -1;

for (int count = 0; count < nodeCount - 1; count++) {


int u = findMinKey(key, visited);
if (u == -1) break; // no unvisited node left
visited[u] = true;

for (int v = 0; v < nodeCount; v++) {


if (adj[u][v] != 0 && !visited[v] && adj[u][v] < key[v]) {
parent[v] = u;
key[v] = adj[u][v];
}
}
}

cout << "\nMinimum Spanning Tree using Prim's Algorithm:\n";


cout << "Edge \tWeight\n";

for (int i = 1; i < nodeCount; i++) {


cout << indexToNode[parent[i]] << " - " << indexToNode[i] << "\t" << adj[i][parent[i]] <<
endl;
totalWeight += adj[i][parent[i]];
}

cout << "\nTotal Weight of MST: " << totalWeight << endl;
}
};

int main() {
int e;
cout << "\nEnter number of Edges: ";
cin >> e;

Graph g(100); // Max 100 nodes

cout << "\nEnter edges (node1 node2 weight):\n";


for (int i = 0; i < e; i++) {
string u, v;
int w;
cin >> u >> v >> w;
[Link](u, v, w);
}

[Link]();

return 0;
}

Test Case 1:
Test Case 2:

Test Case 3:

You might also like