Thread: Help with Minimum Spanning Tree

1. Help with Minimum Spanning Tree

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.

2. A couple of observations.

> for (j=0; j<=n; j++)
To access an array of n elements, you normally write i < n
Unless you have unusual array declarations, this looks a lot like an array overrun.

> if (tree[i])
If tree[i] starts as false, then the only place where this is set to true is INSIDE the test to see if it is true to begin with.
Unreachable code perhaps?