1
00:00:00,420 --> 00:00:04,380
‫So now we're going to talk about the big o of graphs.

2
00:00:04,740 --> 00:00:12,120
‫So I'm going to bring up a graph like this, and we will represent this both as an adjacency matrix

3
00:00:12,120 --> 00:00:14,370
‫and an adjacency list.

4
00:00:14,610 --> 00:00:20,550
‫And we'll look at the big O for both of these, for all of the things that we do with a graph.

5
00:00:20,880 --> 00:00:24,240
‫So we're going to start out by talking about space complexity.

6
00:00:24,240 --> 00:00:34,260
‫So with an adjacency list will store each vertex and the edges it has with other vertices with an adjacency

7
00:00:34,260 --> 00:00:34,800
‫matrix.

8
00:00:34,800 --> 00:00:42,780
‫We are also storing that information, but we also have to store all of the edges that a vertex doesn't

9
00:00:42,780 --> 00:00:44,490
‫have with these zeros.

10
00:00:44,940 --> 00:00:48,810
‫And that is a huge disadvantage of an adjacency matrix.

11
00:00:48,810 --> 00:00:57,750
‫So for space complexity, the adjacency matrix is o of the number of vertices squared versus the adjacency

12
00:00:57,750 --> 00:01:02,640
‫list that is o of the number of vertices plus the number of edges.

13
00:01:02,940 --> 00:01:05,160
‫So now let's look at time complexity.

14
00:01:05,160 --> 00:01:11,610
‫We'll bring back our graph and we'll start by looking at the time complexity to add a vertex.

15
00:01:12,090 --> 00:01:16,770
‫So we'll bring both of these back up and start with the adjacency list.

16
00:01:16,770 --> 00:01:20,010
‫To add a vertex is going to look like this.

17
00:01:20,010 --> 00:01:27,870
‫It's very simple, but with an adjacency matrix to add a vertex, we have to do this.

18
00:01:28,260 --> 00:01:35,100
‫So for storing this with a two dimensional array, we have to completely rebuild this.

19
00:01:35,310 --> 00:01:42,210
‫So from a time complexity perspective, the adjacency matrix is oh of the number of vertices squared

20
00:01:42,210 --> 00:01:48,750
‫because we have to completely rebuild this versus the adjacency list, which is of one.

21
00:01:49,170 --> 00:01:54,870
‫So now let's bring back our graph and look at adding an edge between two vertices.

22
00:01:55,670 --> 00:01:57,440
‫And we'll bring these back up.

23
00:01:57,440 --> 00:02:04,220
‫And first look at doing this with an adjacency list, with an adjacency list to add an edge between

24
00:02:04,220 --> 00:02:05,600
‫B and F.

25
00:02:05,600 --> 00:02:09,560
‫We just need to do this and we need to do this.

26
00:02:10,240 --> 00:02:16,480
‫With an adjacency matrix will change this to a one and we'll change this to a one.

27
00:02:17,020 --> 00:02:21,820
‫So either way, adding an edge is of one.

28
00:02:22,520 --> 00:02:28,520
‫So now let's bring this back and we're going to look at removing an edge between two vertices.

29
00:02:29,330 --> 00:02:30,980
‫It will bring this back up.

30
00:02:30,980 --> 00:02:33,680
‫And we'll start with the adjacency list.

31
00:02:34,130 --> 00:02:43,130
‫To remove the edge between the B and F vertices, we would find B in our unordered map, which is an

32
00:02:43,130 --> 00:02:50,900
‫O of one operation, and then we would remove F from the unordered set that holds those edges.

33
00:02:50,900 --> 00:02:52,970
‫That is also ov one.

34
00:02:53,420 --> 00:03:01,100
‫And then we would find f in our unordered map, another o of one operation, and then remove B from

35
00:03:01,100 --> 00:03:05,330
‫this unordered set, which is another O of one operation.

36
00:03:05,330 --> 00:03:07,550
‫So these are all o of one.

37
00:03:08,240 --> 00:03:15,370
‫With an adjacency matrix will change this to a zero and this two is zero.

38
00:03:15,380 --> 00:03:20,630
‫So for both of these, removing an edge is o of one.

39
00:03:21,020 --> 00:03:26,810
‫So let's bring this back and look at what it takes to remove a vertex.

40
00:03:27,320 --> 00:03:32,090
‫So we'll bring these back up and start with the adjacency list.

41
00:03:32,570 --> 00:03:39,080
‫Now, this looks simple, like we just need to remove this, but if we're going to remove that vertex,

42
00:03:39,080 --> 00:03:45,830
‫we have to start here and make sure that a does not have an edge connecting back to F.

43
00:03:46,470 --> 00:03:52,800
‫And then we need to go to B and make sure it doesn't have an edge connecting back to F and so on.

44
00:03:53,220 --> 00:03:58,980
‫So we're going to have to touch each one of these vertices and make sure it didn't have an edge.

45
00:03:58,980 --> 00:04:03,000
‫Going back to F with an adjacency matrix.

46
00:04:03,000 --> 00:04:10,650
‫In order to remove a vertex, we need to do this, which means that we need to rewrite our two dimensional

47
00:04:10,650 --> 00:04:11,370
‫array.

48
00:04:11,760 --> 00:04:19,950
‫So for removing a vertex, the adjacency matrix is o of the number of vertices squared because we have

49
00:04:19,950 --> 00:04:22,350
‫to rewrite that two dimensional array.

50
00:04:22,620 --> 00:04:29,040
‫And with an adjacency list it is o of the number of vertices because you have to go and touch each one

51
00:04:29,040 --> 00:04:35,220
‫of the vertices to make sure it doesn't have an edge back to the vertex that you removed.

52
00:04:35,990 --> 00:04:42,830
‫So you can see from a big O perspective that the adjacency list is consistently better than the adjacency

53
00:04:42,830 --> 00:04:43,820
‫matrix.

54
00:04:44,420 --> 00:04:50,900
‫The biggest thing with the adjacency matrix is that in addition to storing the edges that you have with

55
00:04:50,900 --> 00:04:56,180
‫other vertices, you also have to store everything that you don't have a connection with.

56
00:04:56,540 --> 00:04:59,850
‫So imagine a very large adjacency matrix.

57
00:04:59,870 --> 00:05:07,250
‫Let's say we're storing Facebook and an adjacency matrix, and each axis, the one across the top and

58
00:05:07,250 --> 00:05:10,730
‫one down the side, has a billion items in it.

59
00:05:11,210 --> 00:05:21,020
‫Even if each user had a thousand friends, there would be a million zeros for every one in the adjacency

60
00:05:21,020 --> 00:05:21,830
‫matrix.

61
00:05:22,310 --> 00:05:29,450
‫So for all of these big reasons, that is why we will be using an adjacency list.

62
00:05:30,020 --> 00:05:33,200
‫And that is our overview of graph.

63
00:05:33,710 --> 00:05:34,820
‫Big O.