Coding is to be done in C++ Randomly create an undirected complete graph as foll
ID: 3688737 • Letter: C
Question
Coding is to be done in C++
Randomly create an undirected complete graph as follows: Create n vertices where n is randomly selected between 5 and 10. Display the selected n value. Create an n times n adjacency matrix A. Randomly assign a weight to each edge (i, j) where 1 lessthanorequalto i, j lessthanorequalto n. Specifically, make A[i, j] = 0 if i = j. If i notequalto j, assign an integer randomly selected between 1 and 10 to A[i,j]. Ensure that A[i, j] = A[j, i] since you need to create an undirected graph. Display the generated adjacency matrix. For the created undirected complete graph, do the following: 1) Implement Prim's minimum spanning tree algorithm by programming priority queue either as array or heap data structure (Chapter 9). Print all the edges in the generated minimum spanning tree. 2) Implement Kruskal's minimum spanning tree algorithm using the find3() and union3() functions in the lecture notes (Chapter 10). Print all the edges in the generated minimum spanning tree. 3) Write a program to find a single source shortest paths using Dijkstra's algorithm. Use vertex 0 as the source. Print all shortest paths from vertex 0 to the other vertices and their lengths.Explanation / Answer
Multiple Questions : Answering 1 :
#include <iostream>
#include <cstdlib> /* srand, rand */
#include <ctime> // time
#include <climits>
#define V 10
using namespace std;
int minKey(int key[], bool mstSet[],int size){
int min = INT_MAX, min_index;
for (int v = 0; v < size; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
int printMST(int parent[], int size ,int graph[V][V]){
cout<<"Edge Weight"<<endl;
for (int i = 1; i < size; i++)
cout<<parent[i]<<" - "<<i<<" "<<graph[i][parent[i]]<<endl;
}
void primMST(int graph[V][V],int size){
int parent[size];
int key[size];
bool mstSet[size];
for (int i = 0; i < size; i++){
key[i] = INT_MAX;
mstSet[i] = false;
}
key[0] = 0; // Make key 0 so that this vertex is picked as first vertex
parent[0] = -1; // First node is always root of MST
for (int count = 0; count < size-1; count++)
{
int u = minKey(key, mstSet,size);
mstSet[u] = true;
for (int v = 0; v < size; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, size, graph);
}
int main(){
srand(2);
int size = (rand()% 6 )+ 5;
int A[V][V];
for(int i=0;i<size;i++){
for(int j=0;j<=i;j++){
if(i == j)
A[i][j] = 0;
else{
A[i][j] = (rand()%11) + 1;
A[j][i] = A[i][j];
}
}
}
for(int i = 0;i<size;i++){
for(int j =0;j<size;j++)
cout<<A[i][j]<<" ";
cout<<endl;
}
primMST(A, size);
return 0;
}