1
00:00:00,620 --> 00:00:05,210
OK, so now we are getting into the meat and bones.

2
00:00:05,780 --> 00:00:14,030
This new subsection of the course, which is going to be about algorithms that are focused on being

3
00:00:14,030 --> 00:00:19,790
used with graphs, so they're not only going to be graphs stuff, but the majority of what we're going

4
00:00:19,790 --> 00:00:23,060
to talk about with these algorithms is going to be associated with graphs.

5
00:00:24,360 --> 00:00:27,840
OK, so what kind of grass are we talking about?

6
00:00:27,870 --> 00:00:34,470
That's what we need to go over in this first lecture is kind of get some things out of the way as far

7
00:00:34,470 --> 00:00:39,480
as explaining what these graphs really are, so we can understand the algorithms that we're going to

8
00:00:39,480 --> 00:00:40,470
go over after this.

9
00:00:41,580 --> 00:00:43,950
So what kind of graphs are we talking about?

10
00:00:44,040 --> 00:00:50,610
Well, you might have used some graphs before and some certain math classes or something where you have

11
00:00:50,610 --> 00:00:54,480
like an x and y axis and some Cartesian coordinates.

12
00:00:54,960 --> 00:00:57,350
We're not talking about those graphs, really.

13
00:00:57,360 --> 00:01:02,550
We're talking about something more aligned with what most people would refer to as graph theory.

14
00:01:03,360 --> 00:01:06,180
And so that is just a collection of vertices and edges.

15
00:01:06,780 --> 00:01:11,100
So you see, we have vertices in green here and edges in blue.

16
00:01:11,730 --> 00:01:18,810
So these are also kind of synonymous with nodes and like the connections between nodes like we did trees,

17
00:01:18,810 --> 00:01:23,370
you know, so we have like a node and then we had like a left and right connection of the binary search

18
00:01:23,370 --> 00:01:28,410
tree to another and another node, you know, like the left child and the right child.

19
00:01:28,890 --> 00:01:30,370
So they're kind of synonymous with that.

20
00:01:30,400 --> 00:01:33,120
You know, here's like a node and here's a connection to another node.

21
00:01:35,880 --> 00:01:43,400
So another important thing is differentiating between directed and undirected graphs.

22
00:01:43,440 --> 00:01:45,210
So here's an undirected graph.

23
00:01:45,210 --> 00:01:53,400
We can basically go from this guy A to B and B to A and then B to C and C to be.

24
00:01:53,400 --> 00:01:54,840
So it's kind of bi directional.

25
00:01:54,870 --> 00:01:56,190
This is not like that, though.

26
00:01:56,460 --> 00:02:00,150
The directed graph, we can go to A to B, but we can't go B to A.

27
00:02:00,450 --> 00:02:03,150
It has some directionality for this edge here, you can see.

28
00:02:03,960 --> 00:02:06,630
And then same thing b c, but not C to be.

29
00:02:09,490 --> 00:02:11,020
And another couple of things.

30
00:02:11,470 --> 00:02:19,810
There are some things called cycles and circuits, a cycle is basically a path where you know, you

31
00:02:19,810 --> 00:02:24,100
choose some kind of starting node here, and that will be the first and last node.

32
00:02:24,430 --> 00:02:31,360
And as you traverse the edges and come back to that node that you will visit, you know you only use

33
00:02:31,360 --> 00:02:32,680
the edges once.

34
00:02:33,280 --> 00:02:38,140
So something like this A to B to C to D to A.

35
00:02:40,240 --> 00:02:47,830
On this, you could also have a cycle if it was like C to B, to A, to B to C, and you don't necessarily

36
00:02:47,830 --> 00:02:54,670
have to have like a square here you could like if you get rid of this edge and this vertex and this

37
00:02:54,670 --> 00:02:57,100
edge and just draw an edge to here.

38
00:02:57,110 --> 00:03:02,410
So it's like a triangle, you know, that would also be a cycle if you want A to B to C back to A.

39
00:03:03,280 --> 00:03:11,340
If we had an inch there and then a circuit is basically like a directed cycle, so we can do that to

40
00:03:11,410 --> 00:03:11,860
restore that.

41
00:03:11,860 --> 00:03:14,740
I just talked about A to B, to C, to D to A.

42
00:03:14,770 --> 00:03:21,340
But we definitely can't do something like C B, a DC because there's directionality to it here.

43
00:03:21,640 --> 00:03:27,400
So basically in directed cycle, this also doesn't have to necessarily be the whole graph like the whole

44
00:03:27,400 --> 00:03:32,410
graph doesn't have to look like this or be, you know, like the whole graph is a cycle.

45
00:03:33,250 --> 00:03:38,290
We can just be a subsection of the graph and we can be talking about a cycle so you can imagine some

46
00:03:38,290 --> 00:03:40,780
more edges and vertices over here.

47
00:03:41,380 --> 00:03:46,750
And this would still be something like that we would refer to as a cycle.

48
00:03:48,850 --> 00:03:52,240
So you might be thinking, Well, is this just like basically trees?

49
00:03:52,240 --> 00:03:58,900
Because we just had, you know, nodes with connections for trees and you pretty much would be right.

50
00:03:58,930 --> 00:04:02,770
The only difference is that a tree is just a graph without a cycle.

51
00:04:02,800 --> 00:04:04,810
So here I'm using that same cycle.

52
00:04:05,650 --> 00:04:09,210
But you know, a tree we could not.

53
00:04:09,220 --> 00:04:12,490
It doesn't necessarily need to be a binary tree.

54
00:04:12,820 --> 00:04:15,470
So, you know, this kind of looks like a binary tree.

55
00:04:15,850 --> 00:04:19,360
We could have like another edge here or something like that.

56
00:04:19,360 --> 00:04:21,550
Or I could even, you know, you could rotate it.

57
00:04:21,550 --> 00:04:25,720
I could even like, make it edge in a vertex like this.

58
00:04:25,750 --> 00:04:26,830
Like, I put a red.

59
00:04:28,170 --> 00:04:30,210
Edge here in another Vertex up here.

60
00:04:31,530 --> 00:04:34,530
And that could still be kind of like a binary choice, even though it looks weird.

61
00:04:34,800 --> 00:04:40,380
But if I draw another line, let's say we have, you know, an edge in a vertex here like I just talked

62
00:04:40,380 --> 00:04:46,380
about, but I draw another edge back to here that could make a cycle going.

63
00:04:46,410 --> 00:04:52,440
You know, you could go A to B to whatever this is back to a that's no longer a tree because it has

64
00:04:52,440 --> 00:04:52,980
a cycle.

65
00:04:54,140 --> 00:04:56,120
So that is the difference between grass and trees.

66
00:04:57,350 --> 00:04:59,000
So how do we represent this in code?

67
00:04:59,030 --> 00:05:05,420
Well, I have a little example graph up here and we're going to be talking about two ways of putting

68
00:05:05,420 --> 00:05:09,290
it in code and adjacency list and an adjacency matrix.

69
00:05:09,950 --> 00:05:14,180
So when I say adjacency, we are talking about something like this.

70
00:05:14,180 --> 00:05:20,000
So a if we start a, we can get from A to B and we can get from A to D.

71
00:05:20,000 --> 00:05:23,360
So B is reachable from A and reachable from A.

72
00:05:23,660 --> 00:05:29,030
We would then say that B and C are adjacent neighbors of A.

73
00:05:29,930 --> 00:05:31,370
So if you look down here.

74
00:05:33,180 --> 00:05:37,050
And I have basically something that is like an array right here.

75
00:05:38,190 --> 00:05:43,170
And then I have linked lists coming off of each one of the indices of disarray.

76
00:05:44,730 --> 00:05:51,810
And so when I look at a for example, again, I have this link list coming off the array and I have

77
00:05:51,810 --> 00:05:57,000
B and which were the adjacent vertices to A.

78
00:05:58,570 --> 00:06:03,190
So that's how the adjacency list is organized is basically you can see here, for example, See has

79
00:06:03,190 --> 00:06:08,270
more neighbors as the B, D, B, E and F.

80
00:06:09,220 --> 00:06:15,220
So that's why we have a link list with all of those adjacent neighbors coming off of this index here

81
00:06:15,220 --> 00:06:15,720
for C.

82
00:06:17,160 --> 00:06:21,420
An adjacency matrix is a great it's a matrix.

83
00:06:22,200 --> 00:06:27,960
So which could be like a two dimensional array or a two dimensional vector or something like that.

84
00:06:29,390 --> 00:06:33,020
It basically says, like, hey, so we're looking again.

85
00:06:33,980 --> 00:06:39,950
I have this column of A. And I'm going to look at all these, I have all of these, all the other vertices

86
00:06:39,950 --> 00:06:40,370
right here.

87
00:06:40,970 --> 00:06:47,420
I put it as zero as in false, if you know, like, for example, here.

88
00:06:48,680 --> 00:06:50,000
A and C.

89
00:06:50,360 --> 00:06:52,220
So C is not adjacent to A..

90
00:06:52,250 --> 00:06:57,800
So for that, I would put a zero for false, but we do have a one here because B is adjacent to a.

91
00:06:58,010 --> 00:07:00,200
Same thing with D D is adjacent a.

92
00:07:00,470 --> 00:07:10,040
So in this cell for Ro D column A. We have a one there for true for C row C column.

93
00:07:10,070 --> 00:07:13,720
We have a zero because a C is not reachable from him.

94
00:07:14,450 --> 00:07:16,730
So same thing with all the rest of them, you know?

95
00:07:16,790 --> 00:07:25,510
See here again, we have B, D, E and F. So B, d e f are all reachable.

96
00:07:25,530 --> 00:07:26,810
That's why those are ones in here.

97
00:07:28,940 --> 00:07:31,010
So why would you choose one over the other?

98
00:07:31,040 --> 00:07:35,570
Well, I'm going to talk about basically two benefits and drawbacks.

99
00:07:36,780 --> 00:07:41,520
Here there are some other ones we can look at, but this is these are the two things that we're going

100
00:07:41,550 --> 00:07:46,470
care about really in the next section, we're doing our algorithms.

101
00:07:47,630 --> 00:07:53,240
So the adjacency list takes up less space, and you can almost just see that visually that it takes

102
00:07:53,240 --> 00:07:53,960
up less space.

103
00:07:55,100 --> 00:08:02,750
So if we're looking at it more specifically, we can say that the adjacency list takes Bigo of the number

104
00:08:02,750 --> 00:08:04,910
of vertices space.

105
00:08:04,910 --> 00:08:08,810
So for a space complexity, it would be big of the number of vertices.

106
00:08:09,410 --> 00:08:13,310
Whereas The Matrix, you know, we see we have a like.

107
00:08:14,200 --> 00:08:19,120
All of our resources right here and all of our resources right here, so we're trying to get the number

108
00:08:19,120 --> 00:08:20,650
of cells in this grid.

109
00:08:21,370 --> 00:08:26,890
It would be this number and this number, which is the same number of times each other.

110
00:08:26,890 --> 00:08:31,480
So this number of times, this number over here, which is basically, you know, this is the number

111
00:08:31,480 --> 00:08:32,320
of vertices.

112
00:08:32,590 --> 00:08:38,320
So it's going to be the big show of the number of vertices squared for our space complexity of the matrix.

113
00:08:39,280 --> 00:08:42,700
So that is a worse complexity and adjacency less.

114
00:08:42,700 --> 00:08:44,170
Therefore, it takes up less space.

115
00:08:45,260 --> 00:08:49,760
Let's look at time complexity, though, so we're talking about searching a given thing, so we want

116
00:08:49,760 --> 00:08:54,680
to know like, hey, like, you know, is C or yeah, let's say.

117
00:08:56,930 --> 00:09:02,430
Let's say is f adjacent to C?

118
00:09:03,260 --> 00:09:08,780
Well, if we go here to the adjacency list, we basically need to be like, OK, you know, maybe we

119
00:09:08,780 --> 00:09:15,680
have this implemented as like a hash table or a hash map or something.

120
00:09:16,280 --> 00:09:20,930
You know, we could be like, All right, I'm a I'm a head of C, so I can jump to see right here cost

121
00:09:20,930 --> 00:09:23,120
and time operation is index it or something like that.

122
00:09:24,040 --> 00:09:28,220
Then I'm like, OK, is f neighbor of C?

123
00:09:28,220 --> 00:09:29,440
Is that adjacent to see?

124
00:09:29,450 --> 00:09:33,650
Well, I have to go through this whole link list and the F is over at the end here.

125
00:09:34,770 --> 00:09:42,810
So ends up boiling down to the adjacency list, having a time complexity for searching for adjacency

126
00:09:42,810 --> 00:09:43,530
of a given.

127
00:09:45,120 --> 00:09:51,570
Vertex being big of the number of vertices she might just have to have, like all of them here in the

128
00:09:51,570 --> 00:09:57,090
linked list, all of the vertices, whereas the adjacency matrix is just constant time because we can

129
00:09:57,090 --> 00:09:58,110
just subscript it.

130
00:09:58,110 --> 00:10:03,720
So, you know, we just have row and then column and it immediately gives us the cell and it's either

131
00:10:03,720 --> 00:10:04,500
one or zero.

132
00:10:05,250 --> 00:10:10,320
So that is then going to be referred to as big of one, which is constant time.

133
00:10:11,970 --> 00:10:13,830
So that's just a basic overview of this.

134
00:10:14,490 --> 00:10:20,400
And that's pretty much all you're going to need to know for this next little section as far as grass.

135
00:10:20,790 --> 00:10:25,470
And then the next video will start getting into some algorithms that not only traverse the graphs,

136
00:10:25,800 --> 00:10:29,370
but have quite quite a few interesting applications as well.

137
00:10:29,520 --> 00:10:31,440
So with that, I will see you in the next lecture.