Prim's Algorithm (Decision Maths)

[tight vine]

can anyone help explain this, don't you always have to check for cycles?

[buoyant pine]

recall how prim's algo works

at each step it adds an edge that connects to a vertex not in the current tree

if a newly added edge had been the edge that completes a cycle, then both vertices incident to it would already have been in our tree, but by construction this cannot happen

[tight vine]

wdym by this "but by construction this cannot happen"?

[buoyant pine]

i mean exactly what i said

it cannot happen that a newly added edge connects a vertex in the tree to another vertex in the tree

because it does not do that

[tight vine]

ahhh yeah, now that i think of it, it makes sense

thanks again

.close