Find Minimum Spanning Tree using Prim's Algorithm of Graph | Representation of Graph using Adjacency List
Problem Statement:- You have a business with several offices; you want to lease phone lines to connect them up with each other, and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connect all your offices with a minimum total cost. Solve the problem by suggesting appropriate data structures.
Note:- Scroll horizontally to see the full line of code.
#include <iostream>
using namespace std;
class flagarray
{
string data;
int flag;
public:
flagarray()
{
this->data = "";
this->flag = 0;
}
flagarray(string data, int flag)
{
this->data = data;
this->flag = flag;
}
friend class node;
friend class graph;
};
class parentarray
{
string data;
string parent;
public:
parentarray()
{
this->data = "";
this->parent = "";
}
friend class node;
friend class graph;
};
class distancearray
{
string data;
int distance;
string fromWhich;
public:
distancearray()
{
this->data = "";
this->distance = 1000;
this->fromWhich = "";
}
friend class node;
friend class graph;
};
class node
{
string data;
int weight;
node *next;
public:
node(string data, int weight)
{
this->data = data;
this->weight = weight;
next = NULL;
}
friend class graph;
};
class graph
{
int vertexCount;
node **cities;
flagarray *setMst;
parentarray *parent;
distancearray *distances;
public:
graph(int vertexCount)
{
this->vertexCount = vertexCount;
setMst = new flagarray[vertexCount];
parent = new parentarray[vertexCount];
distances = new distancearray[vertexCount];
cities = new node *[vertexCount];
for (int i = 0; i < vertexCount; i++)
{
cities[i] = NULL;
}
}
void createGraph();
void display();
void prims();
int indexInCities(string data);
int indexInSetMst(string data);
int indexInParent(string data);
int indexInDistance(string data);
string minDistance();
};
int graph::indexInCities(string data)
{
for (int i = 0; i < vertexCount; i++)
{
if (cities[i]->data == data)
{
return i;
}
}
return -1;
}
int graph::indexInSetMst(string data)
{
for (int i = 0; i < vertexCount; i++)
{
if (setMst[i].data == data)
{
return i;
}
}
return -1;
}
int graph::indexInParent(string data)
{
for (int i = 0; i < vertexCount; i++)
{
if (parent[i].data == data)
{
return i;
}
}
return -1;
}
int graph::indexInDistance(string data)
{
for (int i = 0; i < vertexCount; i++)
{
if (distances[i].data == data)
{
return i;
}
}
return -1;
}
void graph::createGraph()
{
cout << "Enter the no. of Edges: ";
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "Edge " << i + 1 << " : " << endl;
string node1, node2;
int w;
cout << "Enter node 1 of edge: ";
cin >> node1;
cout << "Enter node 2 of edge: ";
cin >> node2;
cout << "Enter the weight of edge: ";
cin >> w;
if (!cities[0])
{
cities[0] = new node(node1, 0);
cities[1] = new node(node2, 0);
setMst[0].data = node1;
parent[0].data = node1;
distances[0].data = node1;
setMst[1].data = node2;
parent[1].data = node2;
distances[1].data = node2;
cities[0]->next = new node(node2, w);
cities[1]->next = new node(node1, w);
}
else
{
int index1 = -1, index2 = -1;
int index = 0;
while (cities[index] && index < vertexCount)
{
if (cities[index]->data == node1)
{
index1 = index;
}
if (cities[index]->data == node2)
{
index2 = index;
}
index++;
}
if (index1 == -1)
{
int j = 0;
while (cities[j])
{
j++;
}
cities[j] = new node(node1, 0);
setMst[j].data = node1;
parent[j].data = node1;
distances[j].data = node1;
cities[j]->next = new node(node2, w);
}
else
{
node *current = cities[index1];
while (current->next)
{
current = current->next;
}
current->next = new node(node2, w);
}
if (index2 == -1)
{
int j = 0;
while (cities[j])
{
j++;
}
cities[j] = new node(node2, 0);
setMst[j].data = node2;
parent[j].data = node2;
distances[j].data = node2;
cities[j]->next = new node(node1, w);
}
else
{
node *current = cities[index2];
while (current->next)
{
current = current->next;
}
current->next = new node(node1, w);
}
}
}
}
void graph::display()
{
if (cities[0])
{
for (int i = 0; i < vertexCount; i++)
{
if (cities[i])
{
node *current = cities[i];
cout << current->data;
if (current->next)
{
current = current->next;
}
while (current)
{
cout << " --> " << current->data << " ( " << current->weight << " ) ";
current = current->next;
}
cout << endl;
}
}
}
else
{
cout << "Graph is Empty!!!" << endl;
}
}
string graph::minDistance()
{
int min = 1001;
int index;
for (int i = 0; i < vertexCount; i++)
{
if (distances[i].distance < min && setMst[indexInSetMst(distances[i].data)].flag == 0)
{
min = distances[i].distance;
index = i;
}
}
return distances[index].data;
}
void graph::prims()
{
distances[indexInDistance(cities[0]->data)].distance = 0;
for (int i = 0; i < vertexCount - 1; i++)
{
string next = minDistance();
setMst[indexInSetMst(next)].flag = 1;
node *current = cities[indexInCities(next)];
while (current)
{
if (!setMst[indexInSetMst(current->data)].flag && current->weight < distances[indexInDistance(current->data)].distance)
{
distances[indexInDistance(current->data)].distance = current->weight;
distances[indexInDistance(current->data)].fromWhich = next;
parent[indexInParent(current->data)].parent = distances[indexInDistance(current->data)].fromWhich;
}
current = current->next;
}
}
int minimumSpanningWeight = 0;
for (int i = 1; i < vertexCount; i++)
{
cout << parent[i].parent << " ---> " << parent[i].data << " : ";
node *current = cities[indexInCities(parent[i].parent)];
while (current)
{
if (current->data == parent[i].data)
{
cout << current->weight << endl;
minimumSpanningWeight += current->weight;
}
current = current->next;
}
}
cout << "Minimum Spanning Weight is : " << minimumSpanningWeight << endl;
}
int main()
{
int n;
cout << "Enter the no. of Vertices: ";
cin >> n;
graph k(n);
k.createGraph();
char cont = 'y';
while (cont == 'y')
{
cout << "<--------Menu-------->" << endl;
cout << "1. Show Adjacency List" << endl;
cout << "2. Minimum Spanning Tree by Prims Algorithm" << endl;
int choice;
cout << "Enter the choice: ";
cin >> choice;
switch (choice)
{
case 1:
cout << "Adjacency List for Graph : " << endl;
k.display();
break;
case 2:
cout << "Minimum Spanning Tree : " << endl;
k.prims();
cout << endl;
break;
default:
cout << "Invalid Choice!!!" << endl;
break;
}
cout << "Do you want to continue ? (y/n) : ";
cin >> cont;
}
cout << "Program Ended Successfully!!!" << endl;
}
Comments
Post a Comment