Problem definition: Give the program that implement Prim’s algorithm. Input: Fir

Question

Problem definition:

Give the program that implement Prim’s algorithm.

Input:
First line is N, denotes the amount of test case, then there are Ns graph data with an option number (determine whether output the selected edges or not).

The first data of each measurement on behalf of the test vertex number, edge number and option number.

Each graph is undirected and connected, it is composed of V (the number of vertices, <= 1000), E (the number of edges, <=10000), then followed by Es edges which are denoted by pair of vertex and weight (e.g., 2 4 10 means an edge connecting vertices 2 and 4, and its weight is 10).

The first data’s weight of each graph is option number. It could be 1 or 2, output the selected edge and the sum of all minimum spanning tree’s weight if it is 1, or only the sum if it is 2.

We restrict that selected node of Prim always start from 0, and there is no “tree edge” with same weight.

Output:
If option is 1:
The selected edges which forms the spanning tree. Order is important! The sum of all edges weight in minimum spanning tree. Note that the edge should put smaller node first, e.g., if the edge (4, 2) is selected, it should be output by 2 4, not 4 2.

If option is 2:
The sum of all edges weight in minimum spanning tree.

Example:
Input:
2

5 7 1

0 2 1

2 1 6

4 2 7

1 4 2

1 3 5

3 0 3

3 2 4

6 12 2

1 0 5

0 4 1

4 5 10

4 3 4

3 0 9

0 5 2

2 0 8

2 1 3

5 2 11

2 3 6

3 5 7

1 5 12

Output: (Prim’s algorithm)

0 2

0 3

1 3

1 4

11

15

please using c++ programming language and follow my INPUT and OUTPUT formats ,thank you .

Explanation / Answer

// We can use effective prims algortihm for finding MST

// STL implementation of Prim's algorithm for MST
#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f

// iPair ==> Integer Pair
typedef pair<int, int> iPair;
int option ;
// This class represents a directed graph using
// adjacency list representation
class Graph
{
   int V; // No. of vertices

   // In a weighted graph, we need to store vertex
   // and weight pair for every edge
   list< pair<int, int> > *adj;

public:
   Graph(int V); // Constructor

   // function to add an edge to graph
   void addEdge(int u, int v, int w);

   // Print MST using Prim's algorithm
   void primMST();
};

// Allocates memory for adjacency list
Graph::Graph(int V)
{
   this->V = V;
   adj = new list<iPair> [V];
}

void Graph::addEdge(int u, int v, int w)
{
   adj[u].push_back(make_pair(v, w));
   adj[v].push_back(make_pair(u, w));
}

// Prints shortest paths from src to all other vertices
void Graph::primMST()
{
   // Create a priority queue to store vertices that
   // are being preinMST. This is weird syntax in C++.
   // Refer below link for details of this syntax
   // http://geeksquiz.com/implement-min-heap-using-stl/
   priority_queue< iPair, vector <iPair> , greater<iPair> > pq;

   int src = 0; // Taking vertex 0 as source

   // Create a vector for keys and initialize all
   // keys as infinite (INF)
   vector<int> key(V, INF);

   // To store parent array which in turn store MST
   vector<int> parent(V, -1);

   // To keep track of vertices included in MST
   vector<bool> inMST(V, false);

   // Insert source itself in priority queue and initialize
   // its key as 0.
   pq.push(make_pair(0, src));
   key[src] = 0;

   /* Looping till priority queue becomes empty */
   while (!pq.empty())
   {
       // The first vertex in pair is the minimum key
       // vertex, extract it from priority queue.
       // vertex label is stored in second of pair (it
       // has to be done this way to keep the vertices
       // sorted key (key must be first item
       // in pair)
       int u = pq.top().second;
       pq.pop();

       inMST[u] = true; // Include vertex in MST

       // 'i' is used to get all adjacent vertices of a vertex
       list< pair<int, int> >::iterator i;
       for (i = adj[u].begin(); i != adj[u].end(); ++i)
       {
           // Get vertex label and weight of current adjacent
           // of u.
           int v = (*i).first;
           int weight = (*i).second;

           // If v is not in MST and weight of (u,v) is smaller
           // than current key of v
           if (inMST[v] == false && key[v] > weight)
           {
               // Updating key of v
               key[v] = weight;
               pq.push(make_pair(key[v], v));
               parent[v] = u;
           }
       }
   }

   // Print edges of MST using parent array
   if(option ==1 ){
   for (int i = 0; i < V; ++i){
       for(int j=1 ; j<V; j++)
       {
       if((parent[j]==i) )
       {printf("%d %d ",i,j ) ;
       parent[j]=-1 ;
       }
       else if ((parent[i])==j)
       {
       printf("%d %d ",i,j ) ;
       parent[i] = -1 ;
      
       }
       }
   }
   }
else
{
int sum = 0 ;
for(int i=0 ; i < V ; i++)
{
sum+=key[i] ;
}
cout<<sum <<endl ;
}
}

// Driver program to test methods of graph class
int main()
{
   // create the graph given in above fugure
   int test;
   cin>>test ;
   while(test--)
   {
   int V,E ;
   cin>>V>>E>>option ;
  
   Graph g(V);

   // making above shown graph
   for(int i =0 ; i<E ; i++){
   int x , y , weight ;
   cin>>x>>y>>weight ;
   g.addEdge(x, y, weight);
   }

   g.primMST();
   }
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.