Write a program to process a weighted undirected graph as follows. (a) Read in t
ID: 3858093 • Letter: W
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.
(b) Set up and print the adjacency matrix representation of the Graph.
(c) Determine whether the graph is connected.
(d) 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
Please refer below code
#include<iostream>
#include <sstream>
#include <string>
#include<fstream>
using namespace std;
int V,E;
void print_adj_mat(double **adj_mat)
{
for(int i=0; i < V; i++)
{
for(int j = 0; j < V; j++)
cout<<adj_mat[i][j]<<" ";
cout<<endl;
}
}
void DFS(int v,int *visited,double **adj_mat)
{
visited[v] = 1;
for(int i = 0; i < V; i++)
{
if(!visited[i] && adj_mat[v][i]!=0 )
DFS(i,visited,adj_mat);
}
}
int main()
{
int u,v;
double w;
double **adj_mat;
char ch;
std::ifstream myfile("graph.txt");
myfile>>V;
myfile>>E;
cout<<"V="<<V<<" "<<"E="<<E<<endl;
adj_mat = new double*[V];
for(int i = 0; i < V; i++)
{
adj_mat[i] = new double[V];
}
for(int i = 0; i < V; i++)
{
for(int j = 0; j < V; j++)
adj_mat[i][j] = 0;
}
//cout<<u<<" "<<v<<endl;
if(myfile.is_open())
{
while(myfile >> u >> ch >> v >> ch >> w)
{
//cout<<u<<" "<<v<<" "<<w<<" "<<endl;
adj_mat[u-1][v-1] = w;
}
}
cout<<"Adjaceny matrix is "<<endl;
print_adj_mat(adj_mat);
int *visited = new int[V];
int flag = 0;
//here we are using DFS to check graph is connected or not.If all the nodes are visited from given node then it's connected
DFS(0,visited,adj_mat);
for(int i=0; i < V; i++)
{
if(visited[i] == 0)
{
cout<<"Not Connected Graph"<<endl;
flag = 1;
break;
}
}
if(!flag)
cout<<"connected Graph"<<endl;
return 0;
}
Please refer below ouput
V=20 E=25
Adjaceny matrix is
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Not Connected Graph
Process returned 0 (0x0) execution time : 0.122 s
Press any key to continue.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.