Write a program to process a weighted undirected graph as follows. (a) Read in t

Question

Write a program to process a weighted undirected graph as follows. (a) Read in the number of vertices V and the number of edges E of the graph followed by its E edges, each in the form u, v, w where 1 <= u, v <= V & w > 0 representing an edge uv with weight w.

Find a minimum spanning tree for each component and print the minimum spanning forest in adjacency matrix representation (regardless it has just one or more than one components). You should document your program, analyze the complexity of your algorithms, and show the outputs from sample data sets in the following.

graph one:

20

25

19,1,3

1,20,5

1,2,7

2,4,7

4,5,10

17,5,5

18,5,20

8,3,3

7,8,2

16,7,6

7,10,5

4,10,7

6,11,6

11,12,10

9,13,12

7,13,10

13,14,8

10,14,50

14,11,100

15,11,12

6,4,5

1,9,20

8,4,15

17,12,33

15,18,5

graph two

10

12

1,9,3

1,2,1.2

2,,5,0.5

2,3,0.8

3,6,3.1

3,10,1.5

4,9,3.2

4,5,1.5

5,7,2

5,8,5.1

10,8,8.8

6,7,5.5

graph three

10

13

1,4,2.3

1,9,1.5

1,5,2.4

7,4,8.3

5,4,3.1

9,5,5.6

7,9,0.8

8,6,3.1

8,2,8.2

2,3,1.5

2,10,6.3

3,6,3.2

3,10,5.6

graph four

15

20

1,3,1.2

1,2,3.1

2,3,2.5

6,7,0.8

6,9,1.2

6,15,9.8

7,9,0.8

7,15,1.1

7,12,3

12,9,2.5

15,12,3.1

4,5,1.2

4,8,3

5,13,1.6

13,8,6.1

11,8,3.2

11,10,1.2

10,8,5.1

10,14,2.1

13,14,3.1

Explanation / Answer

/*

Kruskals algorithm is implemented in order to find the MST.

1.Firstly input is sorted based on the weights of their edges smallest being at the first.
2.Then each edge is taken one by one and checked if its forming a cycle, in case it does, it is discarded else added to MST

Once all MST is found, it is printed in the form of a Adjancency Matrix with:
1. 0 weights from a node to itself
2. -1 in case no direct connection between two nodes.
3. a positive value indicating the value of the weights

Instead of Kruskals, prims algorithm can also be used for the same purpose.
*/

#include <bits/stdc++.h>

/*need algorithm for sort, iostream for input-output,
vector for storing data, utility and algorithms for functions*/

using namespace std;
#define ll long long //macro

int V,E; //no. of vertices, edges

vector < pair <double,pair <int , int > > > Graph; // <weight , < source , destination > >
vector <int> MST;//the vector containing the indexes of edges contributing to MST

int * root; //integer array containing data of roots used in disjoint sets

int roots(int n) // finding the common root in disjoint sets
{
while(root[n] != n)
{
root[n] = root[root[n]];
n = root[n];
}
  
return n;
}

void union1(int i, int j) //union of disjoint sets
{
int x = roots(i);
int y = roots(j);
root[x] = root[y];
}

void kruskal()
/* take the least expensive path and see if it forms a cycle,
in case it does, discard it, else add it*/
{ int s, d; //source , destination
  
double w; //weight
  
for(int i = 0;i < E ;i++)
{
// Selecting edges one by one in increasing order from the beginning

s = Graph[i].second.first;
d = Graph[i].second.second;

w = Graph[i].first;
// Check if the selected edge is creating a cycle or not
  
if(roots(s) != roots(d)) // if forming cycle, their roots will be same
{
           MST.push_back(i);  
           union1(s, d);
}
}
return;
}

void printMST() //printing the MST
{
   double matrix[V+1][V+1]; //adjacency matrix contaning MST
   int s,d; //source
   double w; //destination
  
   for(int i = 0 ; i <=V ; i++) //initializing all to -1
       {for(int j = 0 ; j <= V ; j++)
           {matrix[i][j] = -1;}
           matrix[i][i]=0; //self loop is zero distance
       }

   for(int i = 0 ; i < MST.size();i++) //capturing all those source and destination contributing to MST
   {
       s = Graph[MST[i]].second.first;
d = Graph[MST[i]].second.second;
w = Graph[MST[i]].first;

       matrix[s][d]=w; // filling the adjacency matrix
       matrix[d][s]=matrix[s][d];
   }

   for(int i = 1 ; i <= V ; i++) //printing the adjacency matrix
   {
       for(int j = 1 ; j <=V ; j++)
           cout << matrix[i][j] << " ";
       cout << endl;
   }

}

int main()
{
   int s, d; //source, destination
double w; //weight

cin >> V >> E; //taking number of vertices and edges in graph

root=(int*)malloc((V+1)*sizeof(int)); //allocating memory to

for(int i = 0 ; i <= V ; i++)
   root[i]=i;

Graph.reserve(E); //reserving memory so that can be filled later

for(int i = 0;i < E;i++)
{
cin >> s >> d >> w; //taking inputs and storing in structure with <weights,<source, destination> >

Graph.push_back(make_pair(w, make_pair(s, d)));
}

// Sorting in increasing order of their edge weights
sort(Graph.begin(), Graph.end());

kruskal(); // function call

printMST(); //function call

   return 0;
}

/*
graph one:

20 25
19 1 3
1 20 5
1 2 7
2 4 7
4 5 10
17 5 5
18 5 20
8 3 3
7 8 2
16 7 6
7 10 5
4 10 7
6 11 6
11 12 10
9 13 12
7 13 10
13 14 8
10 14 50
14 11 100
15 11 12
6 4 5
1 9 20
8 4 15
17 12 33
15 18 5

output:

0 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 5
7 0 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 0 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 7 -1 0 10 5 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 10 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 -1 -1 -1
-1 -1 -1 5 -1 0 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 0 2 -1 5 -1 -1 10 -1 -1 6 -1 -1 -1 -1
-1 -1 3 -1 -1 -1 2 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 12 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 7 -1 -1 5 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 6 -1 -1 -1 -1 0 10 -1 -1 12 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10 0 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 10 -1 12 -1 -1 -1 0 8 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 8 0 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12 -1 -1 -1 0 -1 -1 5 -1 -1
-1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1
-1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 -1 -1 0 -1 -1
3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1
5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0

graph two:

10 12
1 9 3
1 2 1.2
2 5 0.5
2 3 0.8
3 6 3.1
3 10 1.5
4 9 3.2
4 5 1.5
5 7 2
5 8 5.1
10 8 8.8
6 7 5.5

output:

0 1.2 -1 -1 -1 -1 -1 -1 3 -1
1.2 0 0.8 -1 0.5 -1 -1 -1 -1 -1
-1 0.8 0 -1 -1 3.1 -1 -1 -1 1.5
-1 -1 -1 0 1.5 -1 -1 -1 -1 -1
-1 0.5 -1 1.5 0 -1 2 5.1 -1 -1
-1 -1 3.1 -1 -1 0 -1 -1 -1 -1
-1 -1 -1 -1 2 -1 0 -1 -1 -1
-1 -1 -1 -1 5.1 -1 -1 0 -1 -1
3 -1 -1 -1 -1 -1 -1 -1 0 -1
-1 -1 1.5 -1 -1 -1 -1 -1 -1 0

graph three:
10 13
1 4 2.3
1 9 1.5
1 5 2.4
7 4 8.3
5 4 3.1
9 5 5.6
7 9 0.8
8 6 3.1
8 2 8.2
2 3 1.5
2 10 6.3
3 6 3.2
3 10 5.6

output:

0 -1 -1 2.3 2.4 -1 -1 -1 1.5 -1
-1 0 1.5 -1 -1 -1 -1 -1 -1 -1
-1 1.5 0 -1 -1 3.2 -1 -1 -1 5.6
2.3 -1 -1 0 -1 -1 -1 -1 -1 -1
2.4 -1 -1 -1 0 -1 -1 -1 -1 -1
-1 -1 3.2 -1 -1 0 -1 3.1 -1 -1
-1 -1 -1 -1 -1 -1 0 -1 0.8 -1
-1 -1 -1 -1 -1 3.1 -1 0 -1 -1
1.5 -1 -1 -1 -1 -1 0.8 -1 0 -1
-1 -1 5.6 -1 -1 -1 -1 -1 -1 0

graph four
15 20
1 3 1.2
1 2 3.1
2 3 2.5
6 7 0.8
6 9 1.2
6 15 9.8
7 9 0.8
7 15 1.1
7 12 3
12 9 2.5
15 12 3.1
4 5 1.2
4 8 3
5 13 1.6
13 8 6.1
11 8 3.2
11 10 1.2
10 8 5.1
10 14 2.1
13 14 3.1

output:

0 -1 1.2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 0 2.5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
1.2 2.5 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 0 1.2 -1 -1 3 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 1.2 0 -1 -1 -1 -1 -1 -1 -1 1.6 -1 -1
-1 -1 -1 -1 -1 0 0.8 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 0.8 0 -1 0.8 -1 -1 -1 -1 -1 1.1
-1 -1 -1 3 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 0.8 -1 0 -1 -1 2.5 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 0 1.2 -1 -1 2.1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 1.2 0 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 2.5 -1 -1 0 -1 -1 -1
-1 -1 -1 -1 1.6 -1 -1 -1 -1 -1 -1 -1 0 3.1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 2.1 -1 -1 3.1 0 -1
-1 -1 -1 -1 -1 -1 1.1 -1 -1 -1 -1 -1 -1 -1 0

*/

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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