Simon is always extremely active in the discussions about the current projects made by/ lectures given by NYU’s Asdociate Professor Daniel Shiffman during his live sessions on the Coding Train channel. He also enjoys “initiating discussions” among the channel’s patrons (grown-up programmers) and Daniel. “Mom, the discussion I initiated is still going on!” I couldn’t possibly post all the coding and math comments/ suggestions that Simon makes in the chats on YouTube, Slack and GitHub (and I don’t believe I should either), but every now and then, I like collecting samples of Simon’s contributing to the discussion:
The small font above says:
Correction: The MST problem does not allow any loops (like A->B, B->C, C->D, D->A again.) So the solution at 2:30 is wrong! In fact, _no wonder it does that_, because Prim’s Algorithm will never find a loop. Here’s why:
Let’s suppose that it could find a loop (let’s say, a loop of 4, so A->B, B->C, C->D, D->A again, but this argument would work the same each way.) Ok, so it will start from A, and mark it as reached. It will check A against B, C and D, find B, and mark B as reached. Then, it will check A against C and D, and B against C and D. and it will find that it should connect B and C, and mark C as reached. Then, it will check A, B and C all against D, and find that it should connect C and D, and mark D as reached. But now, we reach a problem. It will not connect D and A, because both are already reached!
Why was it designed like that? Because that’s what the problem says! It’s a Minimum Spanning _Tree_, so it can’t have any loops.
So there you go, that’s why Prim’s algorithm will not find a loop.
Geeks out of the box 