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).

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

the programming language using c++

Explanation / Answer

Prims Algorithm :

#include<iostream>
#include<stdlib.h>
#include<time.h>

using namespace std;

void Prims(float W[][4], int **T, int N)
{
   int i, j, k;
   // array of nearest node
   int *nearNode = new int[N];
   // array of distance to nearest node
  
   float *minDist = new float[N];
   float min;
   // assume 0 as root node, set it as nearest node to all nodes  
   for (i = 1; i < N; i++) {
       nearNode[i] = 0;
       // set distance of each node from [0]
       minDist[i] = W[i][0];
   }
   // loop for all (N-1) edges
   for (i = 0; i < N-1; i++) {
       min = 999999;
       // find minimum distance
       for (j = 1; j < N; j++) {
           if (0 <= minDist[j] && minDist[j] < min) {
               min = minDist[j];
               // k is closest node
               k = j;
           }
       }
       // update output array - link from nearNode to node
       T[i][0] = nearNode[k];
       T[i][1] = k;
       // k is in the tree; set distance to -1
       minDist[k] = -1;

       // updates all node distances wrt new tree
  
       for (j = 1; j < N; j++)
           if (W[j][k] < minDist[j]) {
               minDist[j] = W[j][k];
               nearNode[j] = k;
           }
   } // for i
   return;
   free(nearNode); free(minDist);
}

int main()
{
   int N;
   float W[4][4];
      
   cout<<"Enter the number of node:";
   cin>>N;

  
   int **t = new int*;
  
   for(int i = 0; i < N; i++)
   {
       t[i] = new int;
   }
  
  
   cout<<"Enter the edges:";
  
   for(int i=0;i<N;i++)
       {
       cout<<"for node:"<<i;
  
   for(int j=0;j<N;j++)
      {
   cin>>W[i][j];     
      }   
   }
  
   Prims(W, t, N);
  
   for(int i = 0; i < N; i++)
   {
       cout << t[i][0] <<" " <<t[i][1] <<endl;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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