1 00:00:00,380 --> 00:00:03,980 ‫So now we're going to write the code to remove a vertex. 2 00:00:04,280 --> 00:00:13,520 ‫And when we remove a vertex, let's say we're going to remove D in order to remove D, we have to remove 3 00:00:13,520 --> 00:00:18,710 ‫all of the edges that D has with the other vertices and the edges. 4 00:00:18,710 --> 00:00:21,500 ‫The other vertices have back to D. 5 00:00:21,800 --> 00:00:26,030 ‫It is only then that we can remove the vertex. 6 00:00:26,950 --> 00:00:28,900 ‫So let's put this back. 7 00:00:28,900 --> 00:00:31,960 ‫We'll put our edges back like that. 8 00:00:32,140 --> 00:00:37,210 ‫And this graph will be represented by this adjacency list. 9 00:00:37,690 --> 00:00:40,630 ‫So let's focus in on this. 10 00:00:41,250 --> 00:00:49,320 ‫So there's an efficiency that we have when we remove a vertex where we have all bi directional edges. 11 00:00:49,770 --> 00:00:58,500 ‫So what we can do is look in this unordered set and if DX has an edge with A, B, and C, we know that 12 00:00:58,500 --> 00:01:01,590 ‫those vertices have an edge back to DX. 13 00:01:01,920 --> 00:01:11,940 ‫So we can loop through this set starting with a and we know that A has an edge back to DX and we can 14 00:01:11,940 --> 00:01:17,880 ‫remove that and that B has an edge back to DX and remove that. 15 00:01:18,300 --> 00:01:25,740 ‫And the same is true for C, and it wouldn't matter if this graph had a thousand vertices in it. 16 00:01:25,950 --> 00:01:32,730 ‫We would only have to visit these three vertices and remove the edges back to DX. 17 00:01:33,090 --> 00:01:37,620 ‫And this only works if we have bidirectional edges. 18 00:01:38,040 --> 00:01:46,440 ‫And once we've removed all of the edges that go back to DX, we can come down here and remove the vertex 19 00:01:47,070 --> 00:01:50,190 ‫and that gives us a graph that looks like this. 20 00:01:50,820 --> 00:01:53,880 ‫So now let's start writing our code. 21 00:01:54,030 --> 00:01:58,170 ‫This will be called Remove Vertex and then we'll just pass it a string. 22 00:01:58,170 --> 00:02:01,080 ‫That is the vertex that we want to remove. 23 00:02:01,620 --> 00:02:07,050 ‫So the first thing we'll do is check to make sure that the vertex is in the adjacency list. 24 00:02:07,050 --> 00:02:11,160 ‫And if it is not, we will return false. 25 00:02:11,640 --> 00:02:15,180 ‫Otherwise, we know the vertex is in the graph. 26 00:02:15,630 --> 00:02:22,710 ‫So the next thing we'll do is create a for loop that loops through the unordered set that is associated 27 00:02:22,710 --> 00:02:25,320 ‫with the vertex that we're removing. 28 00:02:25,890 --> 00:02:33,570 ‫So this line here, adjacency list at the particular vertex, let's just focus in on the for loop here. 29 00:02:33,900 --> 00:02:41,010 ‫What that's going to do is return this unordered set and this is what the for loop is looping through. 30 00:02:41,550 --> 00:02:46,710 ‫So let's put this back in with the rest of our code and inside of the for loop. 31 00:02:47,360 --> 00:02:50,750 ‫We're going to say adjacency list at. 32 00:02:51,490 --> 00:02:55,630 ‫Other vertex and then we'll say dot arrays. 33 00:02:55,960 --> 00:02:57,130 ‫Vertex. 34 00:02:57,220 --> 00:03:00,520 ‫So now let's walk through this line of code. 35 00:03:00,820 --> 00:03:05,350 ‫So let's start with this part adjacency list at other vertex. 36 00:03:05,980 --> 00:03:12,070 ‫Well, this is the variable that's being used to loop through the unordered set down here. 37 00:03:12,610 --> 00:03:16,260 ‫We're starting with a so other vertex. 38 00:03:16,270 --> 00:03:20,440 ‫Is this what this part is going to return? 39 00:03:20,440 --> 00:03:23,590 ‫Is this unordered set? 40 00:03:24,010 --> 00:03:29,800 ‫Erase is one of the member functions associated with unordered sets. 41 00:03:30,280 --> 00:03:34,870 ‫The vertex were removing is D and that removes that. 42 00:03:35,350 --> 00:03:37,750 ‫And remember, this is inside of that for loop. 43 00:03:37,750 --> 00:03:42,100 ‫So we go to B and now that becomes other vertex. 44 00:03:42,460 --> 00:03:45,790 ‫And that removes D from that unordered set. 45 00:03:46,360 --> 00:03:53,200 ‫And then we go to see that is the other vertex and we remove D from here. 46 00:03:53,650 --> 00:03:56,350 ‫So let's bring back the rest of our code. 47 00:03:56,620 --> 00:04:04,300 ‫And now that we've removed all of the edges back to D, now we can do this adjacency list. 48 00:04:04,540 --> 00:04:07,150 ‫Race the vertex. 49 00:04:07,910 --> 00:04:15,620 ‫So that is going to look like this, which gives us a graph that looks like this. 50 00:04:16,710 --> 00:04:21,450 ‫Now the only thing left to do is to return true. 51 00:04:21,930 --> 00:04:25,710 ‫So that is all of the code for remove vertex. 52 00:04:25,740 --> 00:04:28,650 ‫We'll look at this code in a moment and vs code. 53 00:04:28,890 --> 00:04:38,160 ‫And when we do we'll build this graph and then we'll remove the DX vertex and then we'll print the graph 54 00:04:38,160 --> 00:04:41,100 ‫out and we should see something like this. 55 00:04:41,610 --> 00:04:44,940 ‫So now let's flip over and take a look at this. 56 00:04:45,740 --> 00:04:54,770 ‫So there is our remove vertex member function added to our graph class and I'll scroll up and in our 57 00:04:54,770 --> 00:05:02,450 ‫main function this creates our new graph and with these lines we create our vertices A, B, C and D 58 00:05:02,720 --> 00:05:06,830 ‫and with these lines we'll add the edges that we had in the diagram. 59 00:05:06,830 --> 00:05:10,760 ‫And with this line we'll print that out and I'll run this. 60 00:05:11,510 --> 00:05:14,990 ‫And that looks like the graph that we just saw in the diagram. 61 00:05:15,440 --> 00:05:18,440 ‫And now I'm going to come up here and I'm going to add a line. 62 00:05:19,500 --> 00:05:25,020 ‫And with this line we'll remove the D vertex and I will run this. 63 00:05:25,560 --> 00:05:32,250 ‫And you can see up here we have removed the D vertex and all of the edges that go back to D. 64 00:05:33,200 --> 00:05:37,700 ‫And that is our function for remove vertex.