GIVEN CODE:
Prim's algorithm!
#include
#include
#include
using namespace std;
struct Compare
{
bool operator() (const pqData & lhs, const pqData & rhs)
const
{
return (lhs.keyWeight > rhs.keyWeight);
}
};
class resultSetClass {
public:
int parent;
int weight;
resultSetClass() {
parent = -1;
weight = -1;
}
};
class Edge {
public:
int sourceVertex;
int destinationVertex;
int weight;
Edge(int source, int destination, int weight) {
this->sourceVertex = source;
this->destinationVertex = destination;
this->weight = weight;
}
};
class Graph {
private:
int numOfVertices;
Edge** adjListGraph;
public:
Graph() {
this->numOfVertices = 0;
this->adjListGraph = 0;
cout << "Empty Graph Created" << endl;
}
Graph(int numOfVertices) {
this->numOfVertices = numOfVertices;
this->adjListGraph = new Edge*[this->numOfVertices];
for (int i = 0; i < this->numOfVertices; i++) {
this->adjListGraph = 0;
}
}
void addEdge(int source, int destination, int weight) {
if (this->numOfVertices == 0) {
cout << "Empty Graph - Cannot Add Edge: " << source
<< ", " << destination << ", " << weight
<< endl;
}
else if (source < 0 || source >= this->numOfVertices ||
destination < 0 || destination >= this->numOfVertices)
{
cout << "Invalid Source or Destination Vertex - Unable to add
edge: " << source << ", " << destination <<
", " << weight << " - Ignored" << endl;
}
else if (weight <= 0) {
cout << "Invalid Weight - Cannot Add Edge: " << source
<< ", " << destination << ", " << weight
<< " - Ignored" << endl;
}
else {
Edge* edge = new Edge(source, destination, weight);
if (this->adjListGraph[source] == 0) {
this->adjListGraph[source] = edge;
}
else {
Edge* current = this->adjListGraph[source];
while (current->next != 0) {
current = current->next;
}
current->next = edge;
}
cout << "Edge Added: " << source << ", " <<
destination << ", " << weight << endl;
edge = new Edge(destination, source, weight);
if (this->adjListGraph[destination] == 0) {
this->adjListGraph[destination] = edge;
}
else {
Edge* current = this->adjListGraph[destination];
while (current->next != 0) {
current = current->next;
}
current->next = edge;
}
cout << "Edge Added: " << destination << ", "
<< source << ", " << weight << endl;
}
}
void printGraph() {
cout << "Complete Graph - Adj List" << endl;
for (int i = 0; i < this->numOfVertices; i++) {
cout << "Adj[" << i << "] -> ";
Edge* current = this->adjListGraph;
while (current != 0) {
cout << "(" << current->destinationVertex <<
", " << current->weight << ") ";
current = current->next;
}
cout << endl;
}
}
~Graph() {
for (int i = 0; i < this->numOfVertices; i++) {
Edge* current = this->adjListGraph;
while (current != 0) {
Edge* temp = current;
current = current->next;
delete temp;
}
}
delete[] this->adjListGraph;
}
};
- C Program Given Code Prim S Algorithm Include Include Include Using Namespace Std Struct Compare Bool Opera 1 (287.61 KiB) Viewed 48 times
For each graph in the input file data Create full graph Number of vertices and number of edges is first line of each set of graph data if number of vertices less than zero display message "ERROR: number of vertices: <number of vertices> is less than zero" to user and output file display message "Empty Graph Will Be Created" to user and output file create empty graph otherwise if number of vertices is equal to 0 display message "Number of vertices: <number of vertices> is equal to zero" to user and output file display message "Empty Graph Will Be Created" to user and output file create empty graph otherwise vertices value is greater than 0 display message "Number of vertices: <number of vertices> is valid" to user and output file if number of edges is less than number of vertices - 1 (zero or less - input file will have NO edge data; greater than zero but less than number of vertices - 1 cannot be connected graph) display message "ERROR: <number of edges> edges invalid to create connected graph" to user and output file display message "Empty Graph Will Be Created" to user and output file create empty graph if number of edges is less than 0 program will treat as zero edges - file will not contain edges display "Graph with <number of vertices> and <number of edges> will be created" to user and output file create graph with specified number of vertices otherwise
Display "Number of input edges to process is: <number of edges>" to user and output file attempt to add all edges from the input file to the graph if empty graph edges cannot be added display message "Empty Graph - Cannot Add Edge: <source>, <destination>, <weight>" to user and output file if invalid value for vertex (non-existent vertex - negative vertex value, 6 vertices in graph and vertex value is 10) display message "Invalid Source or Destination Vertex - Cannot Add Edge: <source>, <destination>, <weight> - Edge request ignored" to user and output file if invalid value for weight (weight must be greater than 0) display message "Invalid Weight - Cannot Add Edge: <source>, <destination>, <weight> - Edge request ignored" to user and output file otherwise edge can be added to graph undirected graph so there are two edges added to graph adjacency list display message "Edge Added: <source>, <destination>, <weight>" to user and output file display message "Full Graph - Adjacency List" to user and output file For each vertex display graph adjacency list to user and output file in format Adj[vertex] -> (destination1, cost1) (destination2, cost2) Start with vertex 0 add edges to partial MST until complete (Prim's algorithm) using a priority queue Print the full graph adjacency list Create the MST
Print the MST display message "Minimum Spanning Tree" to user and output file if empty graph display message "Empty Graph - No MST" to user and output file otherwise list all edges and weights of the MST display message "Edge: <nbr> - <connected vertex> weight: <edge weight>" to user and output file display message "Total cost of MST: <total MST Weight>" to user and output file display message "MST Graph - Adjacency List" to user and output file for each vertex display MST adjacency list to user and output file in format Adj[vertex] -> (destination1, cost1) (destination2, cost2) Display message "Thank you for running the MST Test Program written by <your name>!" to user and output file