(C) Implement a program in C that uses Prim\'s algorithm to produce a random MST

Question

(C) Implement a program in C that uses Prim's algorithm to produce a random MST (random weights applied to the edges each time, user inputs a perfect square number e.g.: 9 [which would be a 3 x 3 grid graph, or 12 which would be a 4 x 4 grid graph, etc.]) such that the top left node would always be the entrance to the maze and the bottom right nodes would always be the exit of the maze. The resulting grid graph will ultimately be output to the terminal using asterisks to show the maze. The absence of asterisks will be where the nodes are connected. I can post my current code if necessary, but no one has been able to solve this correctly. Anybody who can please answer, or if a tutor can, I'm willing to pay them to show me. I will supply my current code; I think I'm just missing something; my program always segfaults out.

Explanation / Answer

#include<stdio.h>
#include<conio.h>
int b,a,v,u,n,i,j;
int nf=1;
int visitedArr[10]={0},minimum,minimumCost=0,costArr[10][10];
void main()
{
clrscr();
printf(" Enter the no. of nodes:");
scanf("%d",&n);
printf(" Please enter the adjacency matrix: ");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&costArr[i][j]);
if(costArr[i][j]==0)
costArr[i][j]=999;
}
visitedArr[1]=1;
printf(" ");
while(nf<n)
{
for(i=1,minimum=999;i<=n;i++)
for(j=1;j<=n;j++)
if(costArr[i][j]<minimum)
if(visitedArr[i]!=0)
{
minimum=costArr[i][j];
a=i=u;
v=b=j;
}
if(visitedArr[u]==0 || visitedArr[v]==0)
{
printf(" Edge %d : (%d %d) cost : %d", nf++, a, b, minimum);
minimumCost+=minimum;
visitedArr[b]=1;
}
costArr[a][b]=costArr[b][a]=999;
}
printf(" Min costArr=%d",minimumCost);
getch();
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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