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

Answer 1

CODE:

#include <iostream>
using namespace std;
class Graph {
public:
int** adjacencyMatrix; //declare a 2 dimensional array
int vertexCount; //total no of vertex
public:
Graph(int vertexCount) { //initialize graph
this->vertexCount = vertexCount;
adjacencyMatrix = new int*[vertexCount];
for (int i = 0; i < vertexCount; i++) {
adjacencyMatrix[i] = new int[vertexCount];
for (int j = 0; j < vertexCount; j++)
adjacencyMatrix[i][j] = -1; //initialize weight of graph to -1
}
}
//function to add edge
void addEdge(int i, int j,int w) {
if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount) {
adjacencyMatrix[i][j] = w; //add weight to edge
adjacencyMatrix[j][i] = w; //undirected graph weight will be same
}
}


bool isEdge(int i, int j) {
if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount && adjacencyMatrix[i][j]>=0)
{
return true;}
  
else
return false;
}
};

int main() {
   //code
int vt,e,w,i;
int u,v;
cout<<"Enter no of vertices\n";
cin>>vt;
cout<<"Enter no of edges\n";
cin>>e;

Graph g(vt); //create object of graph
//input edge with weight
cout<<"Enter "<<e<<" edges with weight in order (u,v,w)\n";
for(i=0;i<e;i++)
{
cin>>u>>v>>w;
g.addEdge(u,v,w); //add edge to graph
  
}

//print adjacency matrix
cout<<"Adjacency matrix of entered graph :\n";
for(i=0;i<vt;i++)
{
for(int j=0;j<vt;j++)
{
cout<<g.adjacencyMatrix[i][j]<<" ";
}
cout<<"\n";
}
   return 0;
}

OUTPUT:

Enter no of vertices Enter no of edges Enter 25 edges with weight in order (u,v,W) 19 1 3 1 20 5 4 5 10 17 5 5 18 5 20 16 7 6 7 10 5 4 10 7 6 11 6 11 12 10 9 13 12 7 13 16 13 148 1014S® 14 11 100 15 11 12 6 4 5 19 20 8 4 15 17 12 33 15 185