Coding is in C++, Create the graph and solve part 2 of the question, no need to
ID: 3689022 • Letter: C
Question
Coding is in C++, Create the graph and solve part 2 of the question, no need to solve 1 + 3.
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 x n adjacency matrix A. Randomly assign a weight to each edge (i,j) where 1 i, j n. Specifically, make A[i.j] = 0 if i = j. If i j, assign an integer randomly selected between 1 and 10 to ADJ]. Ensure that ADJ] = Ali,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 programing 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
Answer for Question :
What the function of union3() and find() functions. But this below code may help you solving the kruskals algorthim.
This below c++ code is implemeted based on kruskals minimum
spanning tree.
#include<iostream>
#include<conio.h>
using namespace std;
int flag = 0, v[7];
struct node_info
{
int no;
}*q = NULL, *r = NULL;
struct node
{
node_info *pt;
node *next;
}*top = NULL, *p = NULL, *np = NULL;
void push(node_info *ptr)
{
np = new node;
np->pt = ptr;
np->next = NULL;
if (top == NULL)
{
top = np;
}
else
{
np->next = top;
top = np;
}
}
node_info *pop()
{
if (top == NULL)
{
cout<<"underflow ";
}
else
{
p = top;
top = top->next;
return(p->pt);
delete(p);
}
}
int back_edges(int *v,int am[][7],int i,int k)
{
q = new node_info;
q->no = i;
push(q);
v[i] = 1;
for (int j = 0; j < 7; j++)
{
if (am[i][j] == 1 && v[j] == 0)
{
back_edges(v, am, j, i);
}
else if (am[i][j] == 0)
continue;
else if ((j == k) && (am[i][k] == 1 && v[j] == 1))
continue;
else
{
flag = -1;
}
}
r = pop();
return(flag);
}
void init()
{
for (int i = 0; i < 7; i++)
v[i] = 0;
while (top != NULL)
{
pop();
}
}
void kruskals(int am[][7], int wm[][7])
{
int ve = 1, min, temp, temp1;
cout<<"/n/nEDGES CREATED AS FOLLOWS:-/n/n";
while (ve <= 6)
{
min = 999, temp = 0, temp1 = 0;
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7; j++)
{
if ((wm[i][j] < min) && wm[i][j]!=0)
{
min = wm[i][j];
temp = i;
temp1 = j;
}
else if (wm[i][j] == 0)
continue;
}
}
wm[temp][temp1]=wm[temp1][temp] = 999;
am[temp][temp1]=am[temp1][temp] = 1;
init();
if (back_edges(v, am, temp, 0) < 0)
{
am[temp][temp1]=am[temp1][temp] = 0;
flag = 0;
continue;
}
else
{
cout<<"edge created between "<<temp<<" th node and "<<temp1<<" th node"<<endl;
ve++;
}
}
}
int main()
{
int am[7][7], wm[7][7];
for (int i = 0; i < 7; i++)
v[i] = 0;
for (int i = 0; i < 7; i++)
{
for(int j = 0; j < 7; j++)
{
am[i][j] = 0;
}
}
for (int i = 0; i < 7; i++)
{
cout<<"enter the values for weight matrix row:"<<i + 1<<endl;
for(int j = 0; j < 7; j++)
{
cin>>wm[i][j];
}
}
kruskals(am,wm);
getch();
}
Output
enter the values for weight matrix row:1
0
3
6
0
0
0
0
enter the values for weight matrix row:2
3
0
2
4
0
0
0
enter the values for weight matrix row:3
6
2
0
1
4
2
0
enter the values for weight matrix row:4
0
4
1
0
2
0
4
enter the values for weight matrix row:5
0
0
4
2
0
2
1
enter the values for weight matrix row:6
0
0
2
0
2
0
1
enter the values for weight matrix row:7
0
0
0
4
1
1
0
EDGES CREATED AS FOLLOWS:-edge created between 2 th node and 3 th node
edge created between 4 th node and 6 th node
edge created between 5 th node and 6 th node
edge created between 1 th node and 2 th node
edge created between 2 th node and 5 th node
edge created between 0 th node and 1 th node