CONVERT FOLLOWING INTO C++ CODE 1) Algoirthm minimumSpanningTreeKruskal(G) G - A

Question

CONVERT FOLLOWING INTO C++ CODE

1)

Algoirthm minimumSpanningTreeKruskal(G) G - A weighted , undirected graph.

minST = an undirected, weighted graph with the same node set as G, but no edges.

UF = a union-find data structure with the node set of G in which each node is initially in its own subset.

Sort the edges of G in order from smallest to largest weight.

for each edge e=(a,b) in sorted order if UF.find(a) != UF.find(b)

minST.addEdge(a,b)
set the weight of (a,b) in minST to the weight of (a,b) in G UF.union(a,b)

return minST

2)

Algorithm union(a, b)
a, b - elements whose subsets are to be merged

// If a and b are already in the same set, do nothing.

if find(a) == find(b) return

// Otherwise , merge the sets

add the edge (find(a), find(b)) to the union-find graph.

3)

Algorithm find(a)
a - element for which we want to determine set membership

// Follow the chain of directed edges starting from a

x=a
while x has an outgoing edge (x,y) in the union-find graph

x=y

// Since at this point x has no outgoing edge, it must be the // representative element of the set to which a belongs, so

return x

Explanation / Answer

A.

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> iPair;

struct Graph
{
   int A, B;
   vector< pair<int, iPair> > edges;

   Graph(int A, int B)
   {
       this->A = A;
       this->B= B;
   }

   void addEdge(int u, int v, int w)
   {
       edges.push_back({w, {u, v}});
   }

   int kruskalMST();
};

struct DisjointSet
{
   int *parent, *rnk;
   int n;

   DisjointSet(int n)
   {
  
       this->n = n;
       parent = new int[n+1];
       rnk = new int[n+1];

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

          
           parent[i] = i;
       }
   }

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

   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 Graph::kruskalMST()
{
   int mstwt = 0;

  
   sort(edges.begin(), edges.end());

  
   DisjointSet ds(A);

  
   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)
       {
           cout << u << " - " << v << endl;

           mstwt += it->first;

           ds.merge(set_u, set_v);
       }
   }

   return mstwt;
}

int main()
{

   int A = 9, B = 14;
   Graph g(A, B);

   g.addEdge(0, 1, 4);
   g.addEdge(0, 7, 8);
   g.addEdge(1, 2, 8);
   g.addEdge(1, 7, 11);
   g.addEdge(2, 3, 7);
   g.addEdge(2, 8, 2);
   g.addEdge(2, 5, 4);
   g.addEdge(3, 4, 9);
   g.addEdge(3, 5, 14);
   g.addEdge(4, 5, 10);
   g.addEdge(5, 16, 2);
   g.addEdge(16, 7, 1);
   g.addEdge(16, 8, 16);
   g.addEdge(7, 8, 7);

   cout << "Edges of Minimum SPanning Tree are ";
   int mstwt = g.kruskalMST();

   cout << " Weight of MST is " << mstwt;

   return 0;
}

Output:

B.

#include <iostream>   
#include <algorithm>
#include <vector>   

int main () {
int A[] = {5,10,15,20,25};
int B[] = {50,40,30,20,10};
std::vector<int> v(10);
std::vector<int>::iterator it;

std::sort (A,A+5);   
std::sort (B,B+5);   

it=std::set_union (A, A+5, B, B+5, v.begin());

v.resize(it-v.begin());   

std::cout << "There are " << (v.size()) << " elements in union : ";
for (it=v.begin(); it!=v.end(); ++it)
std::cout << ' ' << *it;
std::cout << ' ';

return 0;
}

Output:

C.

#include<iostream>
#include <list>
#include <limits.h>

using namespace std;

class Graph
{
   int A;
   list<int> *a;
   bool isCyclicUtil(int v, bool visited[], bool *rs);
public:
   Graph(int A);
   void addEdge(int v, int w);
   bool isCyclic();
};

Graph::Graph(int A)
{
   this->A = A;
   a = new list<int>[A];
}

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

bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
   if(visited[v] == false)
   {
       visited[v] = true;
       recStack[v] = true;

       list<int>::iterator i;
       for(i = a[v].begin(); i != a[v].end(); ++i)
       {
           if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
               return true;
           else if (recStack[*i])
               return true;
       }

   }
   recStack[v] = false;
   return false;
}

bool Graph::isCyclic()
{
  
   bool *visited = new bool[A];
   bool *recStack = new bool[A];
   for(int i = 0; i < A; i++)
   {
       visited[i] = false;
       recStack[i] = false;
   }

   for(int i = 0; i < A; i++)
       if (isCyclicUtil(i, visited, recStack))
           return true;

   return false;
}

int main()
{
  
   Graph g(4);
   g.addEdge(0, 1);
   g.addEdge(0, 2);
   g.addEdge(1, 2);
   g.addEdge(2, 0);
   g.addEdge(2, 3);
   g.addEdge(3, 3);

   if(g.isCyclic())
       cout << "Graph contains cycle";
   else
       cout << "Graph not contains cycle";
   return 0;
}

Output:

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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