Prim's algorithm

[MrGoodfight]

dick head#

[lktutzi]

At the bottom where you have drawn the minimun spanning tree, Can you draw that in any way you want? This is the bit i am struggling with, When you get a question which says from the matrix use prims and draw the tree? does the tree have to draw in any specific way? Thanks!

[bodil]

@lktutzi You need to connect the new node to the node it came from, so basically connect it to the column letter when you cross it off. E.g. at 0:27 when you cross off D, it's because you've chosen weight 9 from column C. So draw D coming off C in the tree. Draw it as you go, not all at the end. Hope that makes sense :D

[lktutzi]

@bodil yupp sure does Thank you!!! :D

[pkercov07]

The circled ones at the top, are ones that were added to the tree. After adding it cross it's row. So when you look at a row horizontally you need to chose the smallest value that is in the column of the circled ones...easy

[1258585]

I dont understand this AT ALL! >(

[1258585]

@1258585 isn't 7 the smallest weight in row E?! how is it 12?

[pkercov07]

@1258585 7 or in that case F is not in the tree so you can not make a connection EF becouse F is not in the tree, the smallest one that is connected to the tree is 12, so it's BE

[Johannady]

How come EB 12 is chosen and not BD10?

10 is smaller :o

[SymbioteD25]

@Johannady They were both already connected in, so that would have made a cycle.

[sutasman]

just so everyone knows, this is actually a special matrix called the adjacency matrix and as you can see, has the property of being reflective about the topleft-bottomright diagonal

[1nglewattz1]

I got a real stupid question, so I was wondering why did we skip row B, and not go in order to find the smallest number? And, why is the letter D branched out in the line instead of following in between C and E?

[ThePipersDream]

Because after we locate the first lowest value in column A (17 in this example), we go to the column whose row contained that value. I.e. 17 was in column A row C, so we look for our next lowest value in either columns A and C. We then look for our next lowest in any numbered column for the rest of the matrix.

[DiabloUnit13]

@1nglewattz

Not too sure but i would guess that it is because both connections from C-B and C-D have the same weight so they both would apparently attach to C

Like i said not sure but that could be the reason.

[strife133]

Saved my life, Thanks!

[Uniy54]

Pls put it with sound. Thank u

[mushyp102]

this helped me thank you very much!