Now let's turn in the next segment to the Kruskal version. So we'll also talk about, at a high level, what is it that Kruskal does and how it differs from Prim. So Kruskal doesn't necessarily compute a single component. Prim computed a single component and the greedy idea was take the next small edge that adds to that greedy existing component. Kruskal instead creates a forest, which are a set of trees. So each vertex can be thought of to start of as a forest of end nodes, they're not yet connected. And then when you add an edge you take two of the trees in the forest and you turn them into a single component. And so your adding shortest edges. You can sort of view, that the Kruskal algorithm could take the set of edges that are in the graph and sort them, smallest first. Now if you had to sort all the edges of the graph, the graph can have and squared edges. You have a sorting problem there. So N squared, you would end up with something like an N squared log in computation to get the edges sorted as to length. Now you have a sorted list of edges. Why not be able to take the first n minus one edges and create that as your minimum spanning tree? Think about that. That would get you a minimum. So it's clear that those would be the smallest n minus one edges in the graph. The reason is wouldn't necessarily give you a spanning tree is some of those edges may create loops. So, you wouldn't get new edges as you would. You don't get a new node put into the closed set as you do in prim. So, you're forced in the Kruskal Pseudocode to check whether you've created an internal loop. So you can take the next shortest edge, stick it into the existing Kruskal's forest. If it doesn't create a loop, you're fine and go and get the next shortest edge. But you must check, if that next edge is inside a preexisting Kruskal Component, then you have to discard it and move on. Okay, so that's the algorithm. Let's apply it. Here's yet another spanning tree, and this time, we're gonna do Kruskal. So, we would start off, and we know that AD is value five, CE is value five, DF is value six, AB is value seven. BE is 7. EF is 8. BC is 8. BD is nine. EG is nine. FG is 11, and DE is 15. So this is our sorted list of edges. Well, we have no problem. All of the nodes are disconnected at this point. And so, we know we can add this. And now we have our first Kruskal component. AD. Now let me write out the fact that that's a five there. Now we go back to the list. Notice, the next thing we're gonna select is CE, right? Different than Prim. Prim didn't work that way. Prim would have to select DF. It connects up to this component. Kruskal picks the next in the list. It's knocking off these in the list. That's a component that has nothing to do with the pre-existing component. Now the DF is next. So that's six. Let me remember to get all my values. AB 7. Each time in my mind, I'm checking whether I have the edges siting in a Kruskal component. It's not. BE is 7. EF is eight. Notice, I can't draw EF. Why can't I draw EF? It's the next smallest. Cuz it would create a pass. We use a different color for it. We use red. It's a loop. So that can't be used. So, that's thrown out. BC is thrown out. The next one is BD. BD is thrown out. EG is okay. And we're done. That's it. So we have a minimum spanning tree dealing with Kruskal, which built it as a forest. We have 16, 23, 30, 39. MST 39. I said if we wanted to try this let's do it very quickly and with prim and see the difference. I'll start with an A let me get the 5 now there's a 6,7. There is a seven, there is a five and there is a nine. Across goal the supreme would work by building up the component but with does the exact same tree necessarily I think and that would be the same minimum spanning tree as well. Quiz. How would you change this algorithm to find a maximum spanning tree? Maybe you wanna build a tree in which everything is the most costly. That'd be a little unusual so that's not normally how the problem is stated. Okay let's look for a solution. Same structure but instead sort with largest first. You could see the logic of largest first. If there was a spanning tree, you'd get a larger spanning tree. Again, it would have to be a tree structure. It would give you your largest values.
