1
00:00:00,540 --> 00:00:05,880
‫So there are two ways we're going to look at being able to represent a graph.

2
00:00:06,240 --> 00:00:09,810
‫The first one is going to be an adjacency matrix.

3
00:00:09,990 --> 00:00:12,660
‫The other one will be an adjacency list.

4
00:00:12,960 --> 00:00:19,350
‫So let's bring up a graph and we're going to represent this in an adjacency matrix.

5
00:00:19,830 --> 00:00:24,390
‫So we'll start by looking at this a vertex.

6
00:00:24,420 --> 00:00:35,220
‫It has two edges with E and B, so we'll say A has edges with B and E.

7
00:00:35,820 --> 00:00:39,180
‫And we'll just put ones and those boxes there.

8
00:00:39,690 --> 00:00:43,080
‫And of course, A cannot have an edge with itself.

9
00:00:43,080 --> 00:00:47,790
‫So we'll put a zero in that one and that it does not have an edge with C and D.

10
00:00:48,480 --> 00:00:50,220
‫So we'll put zeros in there.

11
00:00:51,110 --> 00:00:53,000
‫Now let's look at B.

12
00:00:53,030 --> 00:00:55,940
‫It has edges with A and C.

13
00:00:56,360 --> 00:00:57,560
‫So B.

14
00:00:58,390 --> 00:01:02,500
‫Has edges with A and C and the rest will be zeros.

15
00:01:03,320 --> 00:01:06,110
‫So I'll just finish building this out like this.

16
00:01:06,680 --> 00:01:08,660
‫To complete our matrix.

17
00:01:10,760 --> 00:01:14,960
‫So this axis represents the actual vertex.

18
00:01:15,260 --> 00:01:20,750
‫This axis is the items it has an edge with.

19
00:01:21,140 --> 00:01:27,110
‫So now one of the things that's interesting about an adjacency matrix, we had mentioned that a can't

20
00:01:27,110 --> 00:01:33,110
‫point to a we'll also be can't point to B and so on.

21
00:01:33,560 --> 00:01:37,760
‫You're always going to have this 45 degree line of zeros.

22
00:01:38,330 --> 00:01:45,950
‫And if you have a bidirectional matrix like we have here, you will always have a mirror image on each

23
00:01:45,950 --> 00:01:50,000
‫side of this 45 degree line that looks like that.

24
00:01:50,650 --> 00:01:52,990
‫But this is only if these are bi directional.

25
00:01:52,990 --> 00:01:57,820
‫So let's change one of these two directional and take a look at that.

26
00:01:58,580 --> 00:02:01,580
‫We have a connection between A and B.

27
00:02:01,940 --> 00:02:09,800
‫So in the matrix that is A connects to B, that's one, B connects back to A that has a one.

28
00:02:10,370 --> 00:02:17,660
‫But if we remove the edge that points from B to A and we change this to A zero.

29
00:02:18,380 --> 00:02:22,850
‫Now we have lost our symmetry across that 45 degree line.

30
00:02:23,360 --> 00:02:29,210
‫So let's change the edge on the graph back to being bidirectional, and then we'll change it in the

31
00:02:29,210 --> 00:02:32,570
‫matrix and now it is symmetrical.

32
00:02:33,170 --> 00:02:37,970
‫So another thing that you can have with your edges is that they can be weighted.

33
00:02:38,210 --> 00:02:46,190
‫So if they're weighted in an adjacency matrix, we will just store these weights in the matrix like

34
00:02:46,190 --> 00:02:48,320
‫this instead of having once.

35
00:02:49,360 --> 00:02:49,550
‫Okay.

36
00:02:49,660 --> 00:02:51,580
‫Let's put that back.

37
00:02:52,390 --> 00:02:56,680
‫And that is our quick overview of an adjacency matrix.