1
00:00:00,550 --> 00:00:00,910
‫Okay.

2
00:00:00,910 --> 00:00:03,400
‫Now let's look at graphs.

3
00:00:03,790 --> 00:00:06,760
‫We're going to start out by bringing this up.

4
00:00:06,970 --> 00:00:10,870
‫This is called a vertex or a node.

5
00:00:10,960 --> 00:00:15,190
‫The proper way to say it is vertex, but you'll hear the word node.

6
00:00:16,060 --> 00:00:18,340
‫And we'll bring up another vertex.

7
00:00:18,880 --> 00:00:21,580
‫The plural would be vertices.

8
00:00:21,790 --> 00:00:28,270
‫Then between the vertices, we have what is called an edge or a connection.

9
00:00:28,630 --> 00:00:30,430
‫The proper way to say it is edge.

10
00:00:30,430 --> 00:00:34,210
‫So we have vertices and edges.

11
00:00:34,570 --> 00:00:36,970
‫Let's bring in another vertex like this.

12
00:00:37,210 --> 00:00:42,910
‫So this vertex can have an edge with this vertex or it can have one.

13
00:00:42,910 --> 00:00:47,050
‫With this one, we're going to have one with both.

14
00:00:47,290 --> 00:00:54,400
‫There is no limit to how many other vertices that a vertex can connect to.

15
00:00:54,610 --> 00:00:58,810
‫So now that we have a small graph, let's look at a couple of concepts.

16
00:00:59,170 --> 00:01:04,030
‫Let's say you want to go from this vertex to this vertex.

17
00:01:04,880 --> 00:01:11,750
‫Well, when you look at this, you would say that you don't want to go this way because that is two

18
00:01:11,780 --> 00:01:12,530
‫hops.

19
00:01:13,240 --> 00:01:18,280
‫And this one is one you'd want to go the more direct route.

20
00:01:18,430 --> 00:01:25,090
‫But with graphs, one of the things you can have you're not always going to have but you can have are

21
00:01:25,090 --> 00:01:26,590
‫weighted edges.

22
00:01:26,890 --> 00:01:34,930
‫So where you would use something like this would be in a maps app you're using Google Maps and the road

23
00:01:34,930 --> 00:01:38,470
‫between 76 and 82 has a lot of traffic.

24
00:01:38,470 --> 00:01:46,840
‫So you go this way instead because this has a cost of five and going this way has a cost of 15.

25
00:01:47,290 --> 00:01:52,480
‫Another place you'll see something like this is with network routing protocols.

26
00:01:52,900 --> 00:01:59,020
‫It would be better to have an extra router hop and have two very fast links than to go the way with

27
00:01:59,020 --> 00:02:00,550
‫a very slow link.

28
00:02:01,090 --> 00:02:04,960
‫And like I said, the edges can be weighted or not weighted.

29
00:02:05,440 --> 00:02:12,160
‫So another concept with graphs which explain this with a Facebook connection between you and a friend.

30
00:02:12,370 --> 00:02:20,410
‫So with a typical Facebook account, your friend is friends with you and you are friends with your friend.

31
00:02:20,410 --> 00:02:23,260
‫It is a bidirectional relationship.

32
00:02:23,500 --> 00:02:30,520
‫So in a graph where all of the edges are bidirectional, you'll often see it like this without arrows.

33
00:02:30,520 --> 00:02:35,860
‫And when you see it like this, it is assumed that it goes both ways.

34
00:02:36,430 --> 00:02:44,050
‫So let's compare this to something like Instagram or Twitter when you follow a celebrity.

35
00:02:44,820 --> 00:02:47,820
‫You are following the celebrity.

36
00:02:47,820 --> 00:02:49,530
‫They don't follow you back.

37
00:02:50,100 --> 00:02:51,540
‫That is directional.

38
00:02:51,930 --> 00:02:55,140
‫So the edges can be weighted or non weighted.

39
00:02:55,470 --> 00:02:58,980
‫They can be directional or bi directional.

40
00:02:59,580 --> 00:03:03,900
‫Also, we have seen a graph in this course.

41
00:03:04,970 --> 00:03:06,050
‫It was a tree.

42
00:03:06,230 --> 00:03:13,970
‫Trees are a form of grafts, but they have the limitation that each node can only point to two other

43
00:03:13,970 --> 00:03:14,750
‫nodes.

44
00:03:14,930 --> 00:03:21,560
‫And when we looked at trees, we had mentioned that we had seen a tree before, which was a linked list.

45
00:03:22,010 --> 00:03:27,530
‫So link lists are a form of a tree, and a tree is a form of a graph.

46
00:03:27,530 --> 00:03:36,020
‫Therefore, a link list is a form of a graph with the limitation that they can only point to one other

47
00:03:36,020 --> 00:03:36,680
‫node.

48
00:03:37,290 --> 00:03:41,340
‫But we typically think of something that looks like this.

49
00:03:41,430 --> 00:03:43,530
‫When we think of graphs.