I've got a majority of this assignment finished, except I'm having an terrible time figuring out how to implement prim's algorithm. I understand it on paper fine and can work it out by hand, coding it is proving difficult though. I've spent quite a few days on this and this is a last ditch effort by posting here.
I'm taking an adjacency matrix from file and creating a minimal spanning tree from it.
lets just say
0 2 4 -1 -1
2 0 4 6 -1
4 4 0 6 4
-1 6 6 0 4
-1 -1 4 4 0
for our purposes here
the -1's represent infinity, because the nodes arent connected in that case.
User gets to pick the starting vertex, so I know that will be the first node in my tree. lets say that vertex happened to be 3. since it's stored as a 2d array, we go down that third row because vertex is 3 and find the smallest distance, which it should find 5 is the smallest right. now from there, you have the third, or the fifth column to find the next smallest item from, because we're now connected to the 5th row. Am I explaining it too unclear?
I can't seem to figure out how to get it to properly comb through all of those
YouTube - Prim's algorithm displays it wonderfully visually, that's kind of what i'm trying to recreate.
Code:
for (j=0; j<=n; j++)
{
int smallestWeight = 100;
for (i=1; i<=n; i++)
{
if (tree[i])
{
if((weight[vertex][i] < smallestWeight) && (weight[vertex][i]>0))
{
smallestWeight=weight[vertex][i];
tree[i]=1;
}
}
}
mst[vertex][i]=smallestWeight;
mst[i][vertex]=smallestWeight;
}
Guidance in the right direction would be fantastic if someone could help.