WEBVTT 00:00:00.251 --> 00:00:01.902 So here's a simple graph. 00:00:01.902 --> 00:00:03.905 We're going to start here with node number 2, 00:00:03.905 --> 00:00:06.182 and we're going to set the depth there equal to 0. 00:00:06.182 --> 00:00:10.290 And our goal is to find these depths for each of these vertices. 00:00:10.290 --> 00:00:12.152 Originally, none of these are set. 00:00:12.152 --> 00:00:14.655 We're just going to say that's the value for hasn't visited yet. 00:00:14.655 --> 00:00:19.321 And we're going to begin by setting vertex number 2 to the value 0. 00:00:19.321 --> 00:00:23.227 So we note that the furthest vertex away from node 2 is two hops away. 00:00:23.227 --> 00:00:27.802 So the maximum depth here is 2, and we should expect that we should iterate twice. 00:00:27.802 --> 00:00:31.537 So we're going to begin the algorithm by looking at all of these edges in parallel. 00:00:31.537 --> 00:00:33.336 And what we're looking for is a pattern 00:00:33.336 --> 00:00:37.708 where one of the vertices of these edges is going to have a depth value set, 00:00:37.708 --> 00:00:39.512 and the other one does not. 00:00:39.512 --> 00:00:42.480 And we're going to find that 3 edges have this particular quality. 00:00:42.480 --> 00:00:45.516 So one of them is going to be the edge between 1 and 2. 00:00:45.516 --> 00:00:47.182 We'll check and see. 00:00:47.182 --> 00:00:53.503 The depth at vertex 2 is 0 and vertex 1 has not been visited yet. 00:00:53.503 --> 00:00:57.231 So we'll set it equal to 0 plus 1, which is 1. 00:00:57.231 --> 00:01:01.131 We'll do the same thing for this edge here between 2 and 3, okay? 00:01:01.131 --> 00:01:03.467 We visited 2; its value was 0. 00:01:03.467 --> 00:01:06.066 We haven't visited 3, so we set its value to be 1. 00:01:06.066 --> 00:01:08.306 And this edge here, 2 and 6. 00:01:08.306 --> 00:01:10.408 Now we complete the first iteration. 00:01:10.408 --> 00:01:12.409 We visited every single edge 00:01:12.409 --> 00:01:16.956 and run 6 threads in parallel to make this particular determination. 00:01:16.956 --> 00:01:18.961 Now we begin our second iteration. 00:01:18.961 --> 00:01:21.217 So now, again, what we're looking for is an edge 00:01:21.217 --> 00:01:24.367 where the vertex value of one end of the edge has been set 00:01:24.367 --> 00:01:26.690 and the other one has not yet been visited. 00:01:26.690 --> 00:01:28.997 So we're going to find that's true for the other 3 edges. 00:01:28.997 --> 00:01:34.501 So the edge between 0 and 1, we find that the depth at vertex number 1 is 1. 00:01:34.501 --> 00:01:37.540 We find that vertex 0 has not yet been visited. 00:01:37.540 --> 00:01:41.305 So we set its depth to 1 plus 1 equals 2. 00:01:41.305 --> 00:01:44.625 And the same is going to be true for the edges between 3 and 4 00:01:44.625 --> 00:01:47.208 and the edge between 5 and 6, okay? 00:01:47.208 --> 00:01:50.287 Now we filled in a value for all of our vertices here, 00:01:50.287 --> 00:01:52.000 and we're thus complete.