Spanning Trees & Prim's Algorithm

[00:00:00]
>> So let's talk about Prim's algorithm. So Prim's algorithm and Kruskal's algorithm are ways to take a graph and turn it into a spanning tree, particularly a minimum spanning tree. So first off, what is a spanning tree? Let's just say we have a four node graph. A spanning tree would be the minimal amount of edges required to have a connection to every single node.

[00:00:26]
So this right here is a spanning tree. This is a spanning tree. This is a spanning tree. That's a spanning tree. Okay, so we get the idea. If you had a graph that looked like this with the floating node, you can't make a spanning tree because we can't visit every single node.

[00:00:43]
So that's a requirement. Now what happened if these edges had weight, 8, 4, 3, 2? Well, if we wanted to make a spanning tree here that was the minimum cost, we'd have to start at any node, doesn't really matter what node. Let's just say we start here, and we want to be able to build out that spanning tree.

[00:01:03]
By the way, spanning trees may or may not all look the same, you could have multiple minimum spanning trees for a single graph, if there's multiple same weight edges along the way. All right, so if we were to just kind of build one with our eyeballs, I think the obvious answer is, don't use eight, right?

[00:01:19]
We are able to do that and the thing about doing this is we are able to do it greedily, right? We could just look at it and go, I already know which ones. That means if we had something here and here and it was a 1 versus a 9, again, you can be as like greedy as you like with these algorithms.

[00:01:35]
I can obviously not take the 9 and clearly take the 1, right? All right, awesome. So this is a spanning tree, we are building a spanning tree. The weight of the spanning tree of course is the sum of all the edges which is 5, 9, 10, it would be 10 that would be the weight, okay?

[00:01:51]
We don't really care, I mean you can care about these for our problems we don't care about them. I actually have, I've never tried to make a minimum spanning tree and then use it in an application, so I don't really know why you do it. I assume every time I hear anything about spanning trees, I just immediately, or anything to do with graphs, I'm just like networking problem and then I just walk away.

[00:02:10]
Like it's usually almost always comes down to networks. Cuz if you really think about it, everything's kind of a network. When you connect them all, you know that one of the original graph problems was, there was a certain set of bridges and some royalty was just like, I want to be able to walk across all these bridges and visit every part of my town without having to cross a bridge more than once.

[00:02:32]
I forget what it was, but I believe Euler then was called. Euler the famous mathematician that we all call Euler. Euler was called and he did a proof and he was just like, you can't actually do this, it's impossible and here's why. Very fantastic. I absolutely love that source.

[00:02:44]
I wanna put down my black marker and we're gonna get another black marker. All right, feeling good. Had to change things up a little bit. All right, so now we are going to do Prim's. So what is Prim's algorithm? Prim's algorithm. And we're also going to compare it with Kruskal's algorithm.

[00:03:04]
All right, so very fantastic. I particularly like this one because this is like almost my whole name right there, so it feels like I'm a part of this algorithm. I have a nice little graph, I just wanna make sure I have it all in my head. I think I have it all in my head.

[00:03:18]
All right, we're gonna be building a minimum spanning tree off the following tree. Look how beautiful. It's a beautifully, please stop clapping, please stop. Man, that's just to kind of everybody. All right,
>> Lots of clapping in the chat.
>> I knew they would chat cuz they like me, unlike some other people here.

[00:03:54]
All right, so, with Prim's algorithm, our goal again is to do a minimum spanning tree and our goal is to do this as quickly as possible. And so Prim's is a greedy algorithm. One of the big differences between Prim's and Kruskal's is with Prim's you start by picking a node, in Kruskal's, you don't pick a node.

[00:04:14]
So we'll first start here. So step one is pick a node. Pick a node, any node, come on, from the audience go.
>> E.
>> E, best node yet. All right, fantastic. Next, we're gonna take and we're gonna add all these edges to a collection. I'm using the term collection intentionally because I want it to be nebulous in the beginning, okay?

[00:04:37]
So add to collection, add edges to collection. We're gonna do a little bit of analyzing on this algorithm, okay? Because graphs are really good to do it and this one, this one right here, this thing right here always catches me every single time I relearn about graphs and trying to understand its runtime, every single time.

[00:04:58]
Absolutely hate this one. All right, after adding e to the collections, we're gonna get smallest edge, remember greedy algorithm, to the smallest edge, edge, smallest edge to unvisited node. And we're gonna just pretty much repeat this, V- 1 times, okay? Because you have already a starting node, and now we just need to do that minus one times, all right?

[00:05:31]
I believe, maybe V times, I'm gonna have to make sure, there's a V -1, maybe I got that wrong. Depending if you count this one as already done or not done, so we're going to do this V times, okay? Pick a starting node, then we do that V times.

[00:05:42]
All right, awesome. So, we start with A, we have visited A, right? So we don't have to add A again. Wait, no, we're starting with e. By the way, I'm very happy you guys said e because e was the node I wanted everyone to start off with, so I've done this 9,000 IQ play all day.

[00:06:00]
All of these are capital letters, this one's lowercase, I was just really trying to make this happen so I'm very excited that you did this for me. All right, there we go, e is selected. Now, we are gonna have this collection that has e to F at a weight of 1, we are going to have a e to G at a weight of 3, and we're gonna have a e to C at a weight of 3.

[00:06:31]
All right, I'm not gonna do that. There we go, so that's our kind of our edges that we need to look at. All right, so now we need to select the lowest edge. First off, our edge weight is infinity, it's now 1, is 1 less than 3? Yes, it is.

[00:06:46]
Is 1 less than 3? Yes, it is. Okay, so this is the edge we're going to pick. I'm going to erase this edge out of here, and we're going to add this edge to our minimum spanning tree. F is now visited, let me just put these on the back.

[00:07:02]
If I was good at this and I've already put them on the back, I'm not good at this and I just drew on myself, I drew on myself. All right, there we go. Now we're gonna do the same thing with F. All right, so we start first with adding the edges.

[00:07:15]
We're going to have F to G at a weight of 2, and we're going to have F to D at a weight of 4, and we're going to have F to E at a weight of 1, but E has already been visited, we don't add it back in.

[00:07:27]
Edge already seen, don't do it. All right, we do it again. E, G, 3, that is our minimum weight right now. All right, it is the equal, so we don't take that one. This one is less than, so this is our new minimum one. Do we take this one?

[00:07:41]
No, it's too large, it's a 4, there we go. So this is the one we're going to be taking, so let's erase that out, that's F to G and so now we do that, fantastic. Again, same thing, G cannot add e, G cannot add F we've already seen them so G is kind of like the nice little terminal experience, we don't need to do anything.

[00:07:59]
So we pick again. E to G, you can't pick that one, G's already been visited, toss it out. Get the hell outta here. E to C haven't been visited, awesome, let's pick this one. F to D, it's larger, it's a 4 versus a 3, so we're gonna keep on picking the smallest one every single time we bring it up here, fantastic.

[00:08:19]
Now we add C, C can do B at a weight of 1, that's a 1 by the way. 7s always contain a cross, 1s don't, that's how you know, and you'll never get mixed up again if you do that. All right, so C to B at a weight of 1.

[00:08:32]
Let's see, C to D at a weight of 8. Can't do the e one, already visited. We've marked C as visited, fantastic. C to B, 1, this is our new minimum weight. Is it less than 8? Yes it is. Is it less than 4? Yes it is. Keep this one right here and now we're gonna pop this one off, fantastic.

[00:08:51]
You're probably thinking I get the algorithm at this point, we're gonna keep on doing it all the way through, okay? It's important to always play algorithms all the way through. All right, B, we can add A to 9, so B, A, 9, B, D, 8. D is not visited yet and there we go.

[00:09:08]
So B, A, 9, 9 is the largest up, this is less than, so we're going to go with this one, C to D for 8, B to D for 8. Notice that if this was reversed, we would have actually chose this one versus this one. But then we get to here F to D it's 4, obviously choose that one, that's the smallest one.

[00:09:24]
So we're gonna go up to here, fantastic. So we do this, now B to A, that's our new lowest one, it's at a 9, up this one's lower, this one's the same. So we choose this one but, hey, this one's already been seen, nothing to do. Again start here, B to A that's a 9, B to D, that's lower, but we've already seen this one.

[00:09:43]
Get this one out of here. Now we go back to here, we see B to A, it's our only choice, this is the one we do. This is the minimum spanning tree, A, B, C, e, F, D, and G, that is the minimum spanning tree. You can kind of just visually prove that this is the smallest amount of weights, and that is how Prim's algorithm works.

[00:10:00]
Does that make sense? Okay, Prim's algorithm is pretty simple in how it works, but we did a lot of things super inefficient, right? Let's just think about our runtime right now. Our runtime is picking a node, constant time. There's also some setup that I didn't really talk about.

[00:10:18]
Like, we have to set up a visited list, the visited list should be the size of V, right? So, that's a V right there. Now, what is the runtime of this statement? We're gonna do a little analysis, I know we haven't done any yet, we're gonna do a little bit here.

[00:10:33]
Graphs just tend to require a lot more analysis. What is the runtime of that statement? Now, one might think, well, we're doing this V times and we have to go over a collection of potentially e elements. Therefore, it is V times e, but you would be wrong, it is not V times e.

[00:10:52]
This is one of those deceptive things that every single time I forget this and I have to relearn it every time I go back to graphs, every single time. Think about it this way. If we go to A, we look at this edge once. When we add B, we look at this edge one more time.

[00:11:11]
We will literally never look at that edge ever again. That means this statement, despite being in a loop, will always be two edge. It is permanently that, 100% of the time, it always executes in two edge because you visit each edge twice. I know, isn't it just the worst?

[00:11:31]
Because it's in a loop and just, it throws me for a loop every single time but it is literally 2e, very cool. Hopefully that blows every last person's mind. Now this one right here, this is the thing that we got to figure out, what is the run time of this?

[00:11:51]
Worst case, we always just say it in worst case, we're not gonna do like a little omega around here, okay? We're just gonna do worst case.
>> Linear because you're searching through the list that you have.
>> Yeah, linear to edge, so it's proportional to the edge, right?

[00:12:04]
And so you could imagine a situation in which you have a graph that has all the edges. And so the first time you do it you have all the edges and then now you're walking over it and worse time. So, this is edge, so that means we are doing something V times e because we have to do this every single time.

[00:12:20]
We will multiple times visit the same edge over and over and over again, like you saw with our A9 business. If we would have started on B, this would have remained in the graph for the entirety of Prim's algorithm, and we would have checked it for every single node.

[00:12:34]
So, it is, right now, our runtime is O of Ve, not great, right? This is not a W right now, we're not winning, okay? We're not loving it.