Question

maximumST is a function that should take an n × n vector (representing the adjacency matrix of a graph) as input and return the value of the maximum spanning tree of the graph defined by the n × n vector.

Code:

#include <vector>

#include <cmath>

#include <iostream>

#include <cstdio>

using namespace std;

double maximumST( vector< vector<double> > adjacencyMatrix ){

  vector<int> row(4,-1);

  vector< vector<int> > matrix(5,row);

  cerr << matrix.size() << endl;

  cerr << matrix[0].size() << endl;

  for( int i = 0; i < 5; i++ ){

    for( int j = 0; j < 4; j++ ){

      fprintf( stderr , "% 2d " , matrix[i][j] );

    }

    cerr << endl;

  }

  return 42.0;

}

C++ please.

Answer 1

Part01.h

#ifndef PART01_H

#define PART01_H

#include <vector>

using namespace std;
double maximumST( vector< vector<double> > );
#endif

.cpp

#include "part01.h"

#include <vector>

#include <queue>

#define pii pair<int, int>
using namespace std;

/**

* Algorithm: Kruskal algorithm to find the minimum spanning tree including disjoint set algorithm for implementation.

* Kruskal Algorithm:

* 1. Sort edges with weights from min to max.

* 2. Remove all the edges from graph

* 3. Now take edges one by one from min weight to max, add one and then check if it forms a loop

* 4. If it doesn't, add it to the graph, else do not add it.

* 5. For a graph with n nodes, after adding n-1 edges, the graph becomes connected without any loops.

*

* Disjoint-set

* 1. For a tree, store the parents of respective nodes.

* 2. Traverse iteratively/recursively to find the respective series of parents.

*/

int parent[10005];

int getParent(int n) {

int x = n;

//Iterative traversal to find the root of the tree

while(parent[n] != n) {

n = parent[n];

}

parent[x] = n;

return n;

}
void setParent(int n,int p) {

int x=n;

//Set the root of the tree as the parent of the node. We maintain the parents such that

//for any node, the value of its parent will be smaller.

while(1) {

x = parent[n];

parent[n] = p;

if(x == n) {

break;

}

n = x;

}

}
double maximumST( vector< vector<double> > graph ){

int n = graph[0].size(), edgeCount = 0, t1, t2;

double weight = 0;

pair<double, pii> p;

vector< pair < double, pii > > v;
//Set the parent of the node itself, as it is still unconnected.

for(int i=0; i<n; i++) {

parent[i] = i;

}
//Create a vector with 3 objects weight, and the vertices of the node

for(int i=0; i<n; i++) {

for(int j=i+1; j<n; j++) {

v.push_back(make_pair(graph[i][j], make_pair(i,j)));

}

}
//Priority queue is a heap. This is a min heap and for every pop, we get an entry of an edge with

//min weight among the existing edges

//priority_queue< pair< double,pii >, vector< pair< double,pii > >, greater<pair< double,pii > > > pq(v.begin(),v.end());
priority_queue< pair< double,pii >, vector< pair< double,pii > > > pq(v.begin(),v.end());

while(edgeCount < n-1) {

p = pq.top();

pq.pop();

t1 = getParent(p.second.first);

t2 = getParent(p.second.second);

//Since we maintain array such that the parent of the node is less than the node,

//we find out the smaller among the parents.

//If the parents are same, that means, adding the current edge with create a cycle. So we ignore it.

if(t1 != t2) {

if(t1 < t2) {

setParent(p.second.second,t1);

} else {

setParent(p.second.first,t2);

}

edgeCount++;

weight += p.first;

}

}
return weight;

}
Sample Input/output:
For input
0 0.5 1 1

0.5 0 3 6

1 3 0 1

1 6 1 0
Output:

The maximum spanning tree value: 10