# 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? Popular pages Recent additions 