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

Question

Problem definition:
Give the program that implement Kruskal’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 minimuspanning 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: (Kruskal’s algorithm)

0 2

1 4

0 3

1 3

11

15

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

Explanation / Answer

Please find the code below.

The description given by you for reading the input is not clear.
First line in the file says number of test cases.

How will I get the total number of vertices and total number of edges for that
test case ? It is not clear.

Also, does the input given by you has 2 test cases ?? I do not see the demarcation
between the first input and second input.

The below CPP code will implement the Kruskal Algorithm.

Please provide the correct input description and input values, so that it can be
read from the file and used in the below program.

#include<bits/stdc++.h>

using namespace std;

// Create shortcut for an integer pair
typedef pair<int, int> iPair;

// Graph Structure.
struct Graph
{
   int V, E;
   vector< pair<int, iPair> > edges;

   Graph(int V, int E)
   {
       this->V = V;
       this->E = E;
   }

   // Function to add an edge
   void addEdgeInfo(int u, int v, int w)
   {
       edges.push_back({w, {u, v}});
   }

   // Function to find MST
   int findMST();
};

// Disjoint Sets structure
struct DisjointSetStructure
{
   int *parent, *rnk;
   int n;

   // Constructor.
   DisjointSetStructure(int n)
   {
       // Allocate memory
       this->n = n;
       parent = new int[n+1];
       rnk = new int[n+1];

       // Initially, all vertices have rank 0
       for (int i = 0; i <= n; i++)
       {
           rnk[i] = 0;
           //every element is parent of itself
           parent[i] = i;
       }
   }

   // Union by rank
   void merge(int x, int y)
   {
       x = find(x), y = find(y);

       if (rnk[x] > rnk[y])
           parent[y] = x;
       else
           parent[x] = y;

       if (rnk[x] == rnk[y])
           rnk[y]++;
   }

   int find(int u)
   {
       if (u != parent[u])
           parent[u] = find(parent[u]);
       return parent[u];
   }
};

/* Functions returns weight of the MST*/

int Graph::findMST()
{
   // Sort edges in increasing order on basis of weights.
   sort(edges.begin(), edges.end());

   int mst_wt = 0;
  
   // Create disjoint sets
   DisjointSetStructure ds(V);

   // Iterate through all sorted edges
   vector< pair<int, iPair> >::iterator it;
  
   for (it=edges.begin(); it!=edges.end(); it++)
   {
       int u = it->second.first;
       int v = it->second.second;

       int set_u = ds.find(u);
       int set_v = ds.find(v);

       if (set_u != set_v)
       {
           // output the edge info.
           cout << u << " - " << v << endl;

           // Update MST weight and merge the two sets.
           mst_wt += it->first;
           ds.merge(set_u, set_v);
       }
   }

   return mst_wt;
}

// Driver program to test above functions
int main()
{
   // Create graph with 9 vertices and 14 edges.
   int V = 9, E = 14;
  
   Graph g(V, E);

   // find the weight info to the Graph.
   g.addEdgeInfo(3, 4, 9);
   g.addEdgeInfo(3, 5, 14);
   g.addEdgeInfo(4, 5, 10);
   g.addEdgeInfo(5, 6, 2);
   g.addEdgeInfo(6, 7, 1);
   g.addEdgeInfo(1, 2, 8);
   g.addEdgeInfo(1, 7, 11);  
   g.addEdgeInfo(2, 5, 4);  
   g.addEdgeInfo(6, 8, 6);
   g.addEdgeInfo(7, 8, 7);
   g.addEdgeInfo(2, 3, 7);
   g.addEdgeInfo(2, 8, 2);
   g.addEdgeInfo(0, 1, 4);
   g.addEdgeInfo(0, 7, 8);
  
   cout << "Edges of MST are ";
   int mstWeight = g.findMST();

   cout << " MST value is " << mstWeight;

   return 0;
}

OUTPUT:
Edges of MST are
6 - 7
2 - 8
5 - 6
0 - 1
2 - 5
2 - 3
0 - 7
3 - 4
  
MST value is 37

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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