[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:11.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:11.00,0:00:14.00,Default,,0000,0000,0000,,This presentation is delivered by the Stanford Center for Professional
Dialogue: 0,0:00:14.00,0:00:25.00,Default,,0000,0000,0000,,Development.
Dialogue: 0,0:00:25.00,0:00:27.00,Default,,0000,0000,0000,,Okay, we got volume and everything. All
Dialogue: 0,0:00:27.00,0:00:28.00,Default,,0000,0000,0000,,right, here we go. Lots of you think your
Dialogue: 0,0:00:28.00,0:00:32.00,Default,,0000,0000,0000,,learning things that aren't gonna actually someday help you in your future
Dialogue: 0,0:00:32.00,0:00:34.00,Default,,0000,0000,0000,,career. Let's say you plan to be president. You
Dialogue: 0,0:00:34.00,0:00:38.00,Default,,0000,0000,0000,,think, ''Should I take 106b; should I not take 106b?'' Watch this interview and
Dialogue: 0,0:00:38.00,0:00:39.00,Default,,0000,0000,0000,,you will see. [Video]
Dialogue: 0,0:00:39.00,0:00:41.00,Default,,0000,0000,0000,,We have questions, and we ask
Dialogue: 0,0:00:41.00,0:00:45.00,Default,,0000,0000,0000,,our candidates questions, and this one is from Larry Schwimmer. What
Dialogue: 0,0:00:45.00,0:00:48.00,Default,,0000,0000,0000,,- you
Dialogue: 0,0:00:48.00,0:00:52.00,Default,,0000,0000,0000,,guys think I'm kidding; it's right here.
Dialogue: 0,0:00:52.00,0:00:59.00,Default,,0000,0000,0000,,What is the most efficient way to sort a million 32-bit integers?
Dialogue: 0,0:00:59.00,0:01:01.00,Default,,0000,0000,0000,,Well - I'm
Dialogue: 0,0:01:01.00,0:01:07.00,Default,,0000,0000,0000,,sorry. Maybe we should - that's not a - I think the bubble sort
Dialogue: 0,0:01:07.00,0:01:09.00,Default,,0000,0000,0000,,would be the wrong way to go. Come on; who told him this?
Dialogue: 0,0:01:09.00,0:01:14.00,Default,,0000,0000,0000,,There you go. So, apparently -
Dialogue: 0,0:01:14.00,0:01:15.00,Default,,0000,0000,0000,,the question was
Dialogue: 0,0:01:15.00,0:01:16.00,Default,,0000,0000,0000,,actually
Dialogue: 0,0:01:16.00,0:01:19.00,Default,,0000,0000,0000,,by a former student of mine, in
Dialogue: 0,0:01:19.00,0:01:22.00,Default,,0000,0000,0000,,fact, Larry Schwimmer. So apparently, he's been prepped well. As part of going on the campaign trail, not only do you
Dialogue: 0,0:01:22.00,0:01:25.00,Default,,0000,0000,0000,,have to know all your policy statements, you also have to have your
Dialogue: 0,0:01:25.00,0:01:29.00,Default,,0000,0000,0000,,N2 and login sorts kept straight in your mind, so - just so
Dialogue: 0,0:01:29.00,0:01:31.00,Default,,0000,0000,0000,,you know. So let me give you
Dialogue: 0,0:01:31.00,0:01:35.00,Default,,0000,0000,0000,,some examples of things that are graphs, just to get you thinking about
Dialogue: 0,0:01:35.00,0:01:36.00,Default,,0000,0000,0000,,
Dialogue: 0,0:01:36.00,0:01:39.00,Default,,0000,0000,0000,,the data structure that we're gonna be working with and playing around with
Dialogue: 0,0:01:39.00,0:01:40.00,Default,,0000,0000,0000,,today. Sometimes you
Dialogue: 0,0:01:40.00,0:01:44.00,Default,,0000,0000,0000,,think of graphs of being those, like, bar graphs, right, your graphing
Dialogue: 0,0:01:44.00,0:01:46.00,Default,,0000,0000,0000,,histograms. This is actually a different kind of graph. The computer scientist's form of
Dialogue: 0,0:01:46.00,0:01:50.00,Default,,0000,0000,0000,,graph is just a generalized, recursive data structure
Dialogue: 0,0:01:50.00,0:01:51.00,Default,,0000,0000,0000,,that, kind of,
Dialogue: 0,0:01:51.00,0:01:54.00,Default,,0000,0000,0000,,starts with something that looks a little bit like a tree and extends it to
Dialogue: 0,0:01:54.00,0:01:55.00,Default,,0000,0000,0000,,this notion that there are
Dialogue: 0,0:01:55.00,0:01:57.00,Default,,0000,0000,0000,,any number of nodes, in
Dialogue: 0,0:01:57.00,0:02:00.00,Default,,0000,0000,0000,,this case, represented as the cities in this airline route map,
Dialogue: 0,0:02:00.00,0:02:04.00,Default,,0000,0000,0000,,and then there are connections between them, sometimes called edges or arcs that wire up
Dialogue: 0,0:02:04.00,0:02:08.00,Default,,0000,0000,0000,,the connections that in the case, for example, of this graph are showing you
Dialogue: 0,0:02:08.00,0:02:10.00,Default,,0000,0000,0000,,which cities have connecting flights. You have a direct
Dialogue: 0,0:02:10.00,0:02:15.00,Default,,0000,0000,0000,,flight that takes you from Las Vegas to Phoenix, right, one from Phoenix to Oklahoma
Dialogue: 0,0:02:15.00,0:02:15.00,Default,,0000,0000,0000,,City.
Dialogue: 0,0:02:15.00,0:02:18.00,Default,,0000,0000,0000,,There is not a direct flight from Phoenix to Kansas City, but there's a path
Dialogue: 0,0:02:18.00,0:02:21.00,Default,,0000,0000,0000,,by which you could get there by taking a sequence
Dialogue: 0,0:02:21.00,0:02:25.00,Default,,0000,0000,0000,,of connecting flights, right, going from Phoenix, to Oklahoma City, to Kansas City is
Dialogue: 0,0:02:25.00,0:02:26.00,Default,,0000,0000,0000,,one way to get there.
Dialogue: 0,0:02:26.00,0:02:30.00,Default,,0000,0000,0000,,And so the entire, kind of, map of airline routes forms a graph of the city,
Dialogue: 0,0:02:30.00,0:02:34.00,Default,,0000,0000,0000,,and there are a lot of interesting questions that having represented that data you might want to
Dialogue: 0,0:02:34.00,0:02:35.00,Default,,0000,0000,0000,,answer about finding
Dialogue: 0,0:02:35.00,0:02:36.00,Default,,0000,0000,0000,,flights that are
Dialogue: 0,0:02:36.00,0:02:40.00,Default,,0000,0000,0000,,cheap, or meet your time specification, or get you where you want to go,
Dialogue: 0,0:02:40.00,0:02:47.00,Default,,0000,0000,0000,,and that this data would be, kind of, primary in solving that problem.
Dialogue: 0,0:02:47.00,0:02:48.00,Default,,0000,0000,0000,,Another one,
Dialogue: 0,0:02:48.00,0:02:49.00,Default,,0000,0000,0000,,right, another
Dialogue: 0,0:02:49.00,0:02:52.00,Default,,0000,0000,0000,,idea of something that's represented as a graph is something that would support
Dialogue: 0,0:02:52.00,0:02:54.00,Default,,0000,0000,0000,,the notion of word ladders, those little puzzles where you're
Dialogue: 0,0:02:54.00,0:02:56.00,Default,,0000,0000,0000,,given the word ''chord,''
Dialogue: 0,0:02:56.00,0:03:00.00,Default,,0000,0000,0000,,and you want to change it into the word ''worm,'' and you have these rules that say, well, you
Dialogue: 0,0:03:00.00,0:03:02.00,Default,,0000,0000,0000,,can change one letter at a time.
Dialogue: 0,0:03:02.00,0:03:04.00,Default,,0000,0000,0000,,And so the
Dialogue: 0,0:03:04.00,0:03:07.00,Default,,0000,0000,0000,,connections in the case of the word letter have to do with words that are
Dialogue: 0,0:03:07.00,0:03:12.00,Default,,0000,0000,0000,,one character different from their neighbors, have direct connections or arcs
Dialogue: 0,0:03:12.00,0:03:16.00,Default,,0000,0000,0000,,between them. Each of the nodes themselves represents a word, and then
Dialogue: 0,0:03:16.00,0:03:19.00,Default,,0000,0000,0000,,paths between that represent word ladders. That if you can go from here
Dialogue: 0,0:03:19.00,0:03:22.00,Default,,0000,0000,0000,,through a sequence of steps directly connecting your way, each of those stepping
Dialogue: 0,0:03:22.00,0:03:26.00,Default,,0000,0000,0000,,stones is a word in the chain that makes a word ladder. So
Dialogue: 0,0:03:26.00,0:03:29.00,Default,,0000,0000,0000,,things you might want to solve there is what's the shortest word ladder? How many different
Dialogue: 0,0:03:29.00,0:03:31.00,Default,,0000,0000,0000,,word ladders - how many different ways can I go from this word to that one
Dialogue: 0,0:03:31.00,0:03:36.00,Default,,0000,0000,0000,,could be answered by searching around in a space like this.
Dialogue: 0,0:03:36.00,0:03:39.00,Default,,0000,0000,0000,,Any kind of prerequisite structure,
Dialogue: 0,0:03:39.00,0:03:42.00,Default,,0000,0000,0000,,such as the one for the major that might say you need to take this class before you take
Dialogue: 0,0:03:42.00,0:03:45.00,Default,,0000,0000,0000,,that class, and this class before that class, right,
Dialogue: 0,0:03:45.00,0:03:46.00,Default,,0000,0000,0000,,forms a
Dialogue: 0,0:03:46.00,0:03:49.00,Default,,0000,0000,0000,,structure that also fits into the main graph.
Dialogue: 0,0:03:49.00,0:03:52.00,Default,,0000,0000,0000,,In this case, there's a connection to those arcs.
Dialogue: 0,0:03:52.00,0:03:54.00,Default,,0000,0000,0000,,That the prerequisite is such that
Dialogue: 0,0:03:54.00,0:03:58.00,Default,,0000,0000,0000,,you take 106a, and it leads into 106b, and that connection doesn't really go in
Dialogue: 0,0:03:58.00,0:04:01.00,Default,,0000,0000,0000,,the reverse, right? You don't start in 106b and move backwards.
Dialogue: 0,0:04:01.00,0:04:05.00,Default,,0000,0000,0000,,Whereas in the case, for example, of the word ladder, all of these arcs are what we called undirected,
Dialogue: 0,0:04:05.00,0:04:09.00,Default,,0000,0000,0000,,right? You can traverse from wood to word and back again, right?
Dialogue: 0,0:04:09.00,0:04:10.00,Default,,0000,0000,0000,,They're equally
Dialogue: 0,0:04:10.00,0:04:12.00,Default,,0000,0000,0000,,
Dialogue: 0,0:04:12.00,0:04:15.00,Default,,0000,0000,0000,,visitable or neighbors, in this case. So there may be a situation where you have directed
Dialogue: 0,0:04:15.00,0:04:20.00,Default,,0000,0000,0000,,arcs where they really imply a one-way directionality through the paths.
Dialogue: 0,0:04:20.00,0:04:22.00,Default,,0000,0000,0000,,Another one, lots and lots of
Dialogue: 0,0:04:22.00,0:04:23.00,Default,,0000,0000,0000,,arrows that
Dialogue: 0,0:04:23.00,0:04:25.00,Default,,0000,0000,0000,,tell you about the lifecycle of
Dialogue: 0,0:04:25.00,0:04:26.00,Default,,0000,0000,0000,,
Dialogue: 0,0:04:26.00,0:04:30.00,Default,,0000,0000,0000,,Stanford relationships all captured on one
Dialogue: 0,0:04:30.00,0:04:31.00,Default,,0000,0000,0000,,slide
Dialogue: 0,0:04:31.00,0:04:34.00,Default,,0000,0000,0000,,in, sort of, the flowchart. So flowcharts have a lot of things about directionality. Like, you're
Dialogue: 0,0:04:34.00,0:04:37.00,Default,,0000,0000,0000,,in this state, and you can move to this state, so that's your neighboring state, and
Dialogue: 0,0:04:37.00,0:04:39.00,Default,,0000,0000,0000,,the arcs in there connect those things.
Dialogue: 0,0:04:39.00,0:04:43.00,Default,,0000,0000,0000,,And so, as you will see, like, you get to start over here and, like, be single and love
Dialogue: 0,0:04:43.00,0:04:47.00,Default,,0000,0000,0000,,it, and then you can, kind of, flirt with various degrees of seriousness,
Dialogue: 0,0:04:47.00,0:04:50.00,Default,,0000,0000,0000,,and then eventually there evolves a trombone and serenade, which, you know,
Dialogue: 0,0:04:50.00,0:04:53.00,Default,,0000,0000,0000,,you can't go back to flirting aimlessly after the trombone and serenade; there's no
Dialogue: 0,0:04:53.00,0:04:55.00,Default,,0000,0000,0000,,arc that direction.
Dialogue: 0,0:04:55.00,0:04:57.00,Default,,0000,0000,0000,,When somebody gets the trombone out,
Dialogue: 0,0:04:57.00,0:04:59.00,Default,,0000,0000,0000,,you know, you take them seriously,
Dialogue: 0,0:04:59.00,0:05:02.00,Default,,0000,0000,0000,,or you completely blow them off. There's the [inaudible] there.
Dialogue: 0,0:05:02.00,0:05:04.00,Default,,0000,0000,0000,,And then there's dating, and then there's
Dialogue: 0,0:05:04.00,0:05:08.00,Default,,0000,0000,0000,,two-phase commit, which is a very important part of any computer scientist's education,
Dialogue: 0,0:05:08.00,0:05:10.00,Default,,0000,0000,0000,,and then, potentially, other
Dialogue: 0,0:05:10.00,0:05:13.00,Default,,0000,0000,0000,,tracks of children and what not. But it does
Dialogue: 0,0:05:13.00,0:05:15.00,Default,,0000,0000,0000,,show you, kind of, places you can go, right?
Dialogue: 0,0:05:15.00,0:05:18.00,Default,,0000,0000,0000,,It turns out you actually don't get to go from flirt aimlessly to have baby, so
Dialogue: 0,0:05:18.00,0:05:20.00,Default,,0000,0000,0000,,write that down -
Dialogue: 0,0:05:20.00,0:05:23.00,Default,,0000,0000,0000,,not allowed in this graph. And
Dialogue: 0,0:05:23.00,0:05:28.00,Default,,0000,0000,0000,,then it turns out some things that you've already seen are actually graphs in disguise.
Dialogue: 0,0:05:28.00,0:05:32.00,Default,,0000,0000,0000,,I didn't tell you when I gave you the maze problem and its solution, the solving and
Dialogue: 0,0:05:32.00,0:05:33.00,Default,,0000,0000,0000,,building of a maze,
Dialogue: 0,0:05:33.00,0:05:37.00,Default,,0000,0000,0000,,that, in fact, what you're working on though is something that is a graph.
Dialogue: 0,0:05:37.00,0:05:39.00,Default,,0000,0000,0000,,That a perfect maze, right,
Dialogue: 0,0:05:39.00,0:05:40.00,Default,,0000,0000,0000,,so we started with this
Dialogue: 0,0:05:40.00,0:05:44.00,Default,,0000,0000,0000,,fully disconnected maze. If you remember how the Aldis/Broder algorithm worked, it's like
Dialogue: 0,0:05:44.00,0:05:47.00,Default,,0000,0000,0000,,you have all these nodes that have no connections between them,
Dialogue: 0,0:05:47.00,0:05:51.00,Default,,0000,0000,0000,,and then you went bopping around breaking down walls, which is effectively
Dialogue: 0,0:05:51.00,0:05:53.00,Default,,0000,0000,0000,,connecting up the nodes to each other,
Dialogue: 0,0:05:53.00,0:05:57.00,Default,,0000,0000,0000,,and we kept doing that until actually all of the nodes were connected. So, in effect, we
Dialogue: 0,0:05:57.00,0:06:00.00,Default,,0000,0000,0000,,were building a graph out of this big grid of cells
Dialogue: 0,0:06:00.00,0:06:03.00,Default,,0000,0000,0000,,by knocking down those walls to build the connections, and when we were done, then
Dialogue: 0,0:06:03.00,0:06:07.00,Default,,0000,0000,0000,,we made it so that it was possible to trace paths starting from that lower corner
Dialogue: 0,0:06:07.00,0:06:10.00,Default,,0000,0000,0000,,and working our way through the neighbors all the way over to there.
Dialogue: 0,0:06:10.00,0:06:13.00,Default,,0000,0000,0000,,So in the case of this, if you imagine that each of these cells was broken out in this little
Dialogue: 0,0:06:13.00,0:06:16.00,Default,,0000,0000,0000,,thing, there'd be these neighboring connections where this guy has this
Dialogue: 0,0:06:16.00,0:06:19.00,Default,,0000,0000,0000,,neighbor but no other ones because actually it has no
Dialogue: 0,0:06:19.00,0:06:22.00,Default,,0000,0000,0000,,other directions you can move from there, but some of them, for example like this
Dialogue: 0,0:06:22.00,0:06:23.00,Default,,0000,0000,0000,,one,
Dialogue: 0,0:06:23.00,0:06:26.00,Default,,0000,0000,0000,,has a full set of four neighbors you can reach
Dialogue: 0,0:06:26.00,0:06:28.00,Default,,0000,0000,0000,,depending on which walls are intact or not.
Dialogue: 0,0:06:28.00,0:06:29.00,Default,,0000,0000,0000,,And so the
Dialogue: 0,0:06:29.00,0:06:31.00,Default,,0000,0000,0000,,creation of that was creating a graph out
Dialogue: 0,0:06:31.00,0:06:34.00,Default,,0000,0000,0000,,of a set of disconnected nodes, and then solving it is searching that
Dialogue: 0,0:06:34.00,0:06:38.00,Default,,0000,0000,0000,,graph for a path. Here's one that is a little horrifying that came from the newspaper, which is social networking, kind of, a very big [inaudible] of, like, on the net who do you know, and who do they know, and how do those connections, like, linked in maybe help you get a job. This is one that was actually based on the liaisons, let's say, of a group of high school students, right, and it turns out there was a lot of more interconnected in that graph than I would expect, or appreciate, or approve of but interesting to, kind of, look at. So
Dialogue: 0,0:06:38.00,0:06:39.00,Default,,0000,0000,0000,,let's talk, like, concretely.
Dialogue: 0,0:06:39.00,0:06:43.00,Default,,0000,0000,0000,,How are we gonna make stuff work on graphs? Graphs turn out to actually - by showing you that, I'm trying to
Dialogue: 0,0:06:43.00,0:06:46.00,Default,,0000,0000,0000,,get you this idea that a lot of things are really just graphs in disguise. That a lot
Dialogue: 0,0:06:46.00,0:06:50.00,Default,,0000,0000,0000,,of the problems you may want to solve, if you can represent it as a graph, then things
Dialogue: 0,0:06:50.00,0:06:53.00,Default,,0000,0000,0000,,you learn about how to manipulate graphs will help you to solve that kind of
Dialogue: 0,0:06:53.00,0:06:54.00,Default,,0000,0000,0000,,problem.
Dialogue: 0,0:06:54.00,0:06:59.00,Default,,0000,0000,0000,,So the basic idea of a graph, it is a recursive data structure based on the node where
Dialogue: 0,0:06:59.00,0:07:02.00,Default,,0000,0000,0000,,nodes have connections to other nodes.
Dialogue: 0,0:07:02.00,0:07:04.00,Default,,0000,0000,0000,,Okay. So that's, kind of, like a tree,
Dialogue: 0,0:07:04.00,0:07:07.00,Default,,0000,0000,0000,,but it actually is more freeform than a tree, right?
Dialogue: 0,0:07:07.00,0:07:11.00,Default,,0000,0000,0000,,In a tree, right, there's that single root node that has, kind of, a special place, and
Dialogue: 0,0:07:11.00,0:07:15.00,Default,,0000,0000,0000,,there's this restriction about the connections that there's a single path
Dialogue: 0,0:07:15.00,0:07:17.00,Default,,0000,0000,0000,,from every other node in the tree
Dialogue: 0,0:07:17.00,0:07:20.00,Default,,0000,0000,0000,,starting from the root that leads to it. So you never can get there by
Dialogue: 0,0:07:20.00,0:07:24.00,Default,,0000,0000,0000,,multiple ways, and there's no cycles, and it's all connected, and things like
Dialogue: 0,0:07:24.00,0:07:25.00,Default,,0000,0000,0000,,that.
Dialogue: 0,0:07:25.00,0:07:26.00,Default,,0000,0000,0000,,So, in terms of a graph,
Dialogue: 0,0:07:26.00,0:07:29.00,Default,,0000,0000,0000,,it just doesn't place those restrictions. It says there's a node.
Dialogue: 0,0:07:29.00,0:07:32.00,Default,,0000,0000,0000,,It has any number of pointers to other nodes. It potentially could even
Dialogue: 0,0:07:32.00,0:07:36.00,Default,,0000,0000,0000,,have zero pointers to other's nodes, so it could be on a little island of its own out
Dialogue: 0,0:07:36.00,0:07:38.00,Default,,0000,0000,0000,,here that has no incoming or outgoing flights, right? You
Dialogue: 0,0:07:38.00,0:07:40.00,Default,,0000,0000,0000,,have to swim if you want to get there.
Dialogue: 0,0:07:40.00,0:07:42.00,Default,,0000,0000,0000,,
Dialogue: 0,0:07:42.00,0:07:45.00,Default,,0000,0000,0000,,And then there's also not a rule that says that you can't have
Dialogue: 0,0:07:45.00,0:07:47.00,Default,,0000,0000,0000,,multiple ways to get to the same
Dialogue: 0,0:07:47.00,0:07:50.00,Default,,0000,0000,0000,,node. So if you're at B, and you're interested in getting to C,
Dialogue: 0,0:07:50.00,0:07:52.00,Default,,0000,0000,0000,,you could take the direction connection here,
Dialogue: 0,0:07:52.00,0:07:54.00,Default,,0000,0000,0000,,but you could also take a longer path
Dialogue: 0,0:07:54.00,0:07:58.00,Default,,0000,0000,0000,,that bops through A and hits to C, and so there's more than one way to get there,
Dialogue: 0,0:07:58.00,0:07:59.00,Default,,0000,0000,0000,,
Dialogue: 0,0:07:59.00,0:08:02.00,Default,,0000,0000,0000,,which would not be true in a tree structure where it has that constraint,
Dialogue: 0,0:08:02.00,0:08:05.00,Default,,0000,0000,0000,,but that adds some interesting challenges to solving problems in the graphs
Dialogue: 0,0:08:05.00,0:08:08.00,Default,,0000,0000,0000,,because there actually are so many different ways you can
Dialogue: 0,0:08:08.00,0:08:11.00,Default,,0000,0000,0000,,get to the same place. We have to be careful avoiding
Dialogue: 0,0:08:11.00,0:08:13.00,Default,,0000,0000,0000,,getting into circularities where we're
Dialogue: 0,0:08:13.00,0:08:16.00,Default,,0000,0000,0000,,doing that, and also not redundantly doing work we've already done before because
Dialogue: 0,0:08:16.00,0:08:18.00,Default,,0000,0000,0000,,we've visited it previously.
Dialogue: 0,0:08:18.00,0:08:21.00,Default,,0000,0000,0000,,There can be cycles where
Dialogue: 0,0:08:21.00,0:08:22.00,Default,,0000,0000,0000,,you can
Dialogue: 0,0:08:22.00,0:08:24.00,Default,,0000,0000,0000,,completely come around. I this one, actually,
Dialogue: 0,0:08:24.00,0:08:26.00,Default,,0000,0000,0000,,doesn't have a cycle in it.
Dialogue: 0,0:08:26.00,0:08:27.00,Default,,0000,0000,0000,,Nope, it doesn't,
Dialogue: 0,0:08:27.00,0:08:31.00,Default,,0000,0000,0000,,but if I add it - I could add a link, for example, from
Dialogue: 0,0:08:31.00,0:08:34.00,Default,,0000,0000,0000,,C back to B, and then there would be this place you could just, kind of, keep
Dialogue: 0,0:08:34.00,0:08:36.00,Default,,0000,0000,0000,,rolling around in the B, A, C
Dialogue: 0,0:08:36.00,0:08:38.00,Default,,0000,0000,0000,,area.
Dialogue: 0,0:08:38.00,0:08:41.00,Default,,0000,0000,0000,,So we call each of those guys, the circles here, the nodes, right?
Dialogue: 0,0:08:41.00,0:08:44.00,Default,,0000,0000,0000,,The connection between them arcs. We
Dialogue: 0,0:08:44.00,0:08:47.00,Default,,0000,0000,0000,,will talk about the arcs as being directed and undirected in different situations
Dialogue: 0,0:08:47.00,0:08:51.00,Default,,0000,0000,0000,,where we imply that there's a directionality; you can travel the arc only one-way,
Dialogue: 0,0:08:51.00,0:08:54.00,Default,,0000,0000,0000,,or in cases where it's undirected, it means it goes both ways.
Dialogue: 0,0:08:54.00,0:08:56.00,Default,,0000,0000,0000,,We'll talk about two nodes being connected,
Dialogue: 0,0:08:56.00,0:08:58.00,Default,,0000,0000,0000,,meaning there is a direct connection, an arc, between them,
Dialogue: 0,0:08:58.00,0:09:02.00,Default,,0000,0000,0000,,and if they are not directly connected, there may possibly be a path
Dialogue: 0,0:09:02.00,0:09:05.00,Default,,0000,0000,0000,,between them. A sequence of arcs forms a path that you can follow to get
Dialogue: 0,0:09:05.00,0:09:07.00,Default,,0000,0000,0000,,from one node to another,
Dialogue: 0,0:09:07.00,0:09:11.00,Default,,0000,0000,0000,,and then cycles just meaning a path that revisits one of the nodes that
Dialogue: 0,0:09:11.00,0:09:14.00,Default,,0000,0000,0000,,was previously traveled on that path. So I've got
Dialogue: 0,0:09:14.00,0:09:16.00,Default,,0000,0000,0000,,a little terminology.
Dialogue: 0,0:09:16.00,0:09:18.00,Default,,0000,0000,0000,,Let's talk a little bit about how we're gonna represent it.
Dialogue: 0,0:09:18.00,0:09:22.00,Default,,0000,0000,0000,,So before we start making stuff happen on them, it's, like, well, how does this -
Dialogue: 0,0:09:22.00,0:09:26.00,Default,,0000,0000,0000,,in C++, right, what's the best way, or what are the reasonable ways you
Dialogue: 0,0:09:26.00,0:09:27.00,Default,,0000,0000,0000,,might represent
Dialogue: 0,0:09:27.00,0:09:30.00,Default,,0000,0000,0000,,this kind of connected structure?
Dialogue: 0,0:09:30.00,0:09:31.00,Default,,0000,0000,0000,,So if I have
Dialogue: 0,0:09:31.00,0:09:36.00,Default,,0000,0000,0000,,this four-node graph, A, B, C, D over where with the connections that are shown with
Dialogue: 0,0:09:36.00,0:09:38.00,Default,,0000,0000,0000,,direction, in this case, I have directed arcs.
Dialogue: 0,0:09:38.00,0:09:41.00,Default,,0000,0000,0000,,That one way to think of it is that what a
Dialogue: 0,0:09:41.00,0:09:45.00,Default,,0000,0000,0000,,graph really is is a set of nodes and a set of arcs, and by set, I mean, sort of, just the
Dialogue: 0,0:09:45.00,0:09:48.00,Default,,0000,0000,0000,,generalization. There might be a vector of arcs; there might be a vector of
Dialogue: 0,0:09:48.00,0:09:51.00,Default,,0000,0000,0000,,nodes, whatever, but some collection of arcs, some collection of nodes,
Dialogue: 0,0:09:51.00,0:09:53.00,Default,,0000,0000,0000,,and that the
Dialogue: 0,0:09:53.00,0:09:56.00,Default,,0000,0000,0000,,nodes might have information about what location they represent, or
Dialogue: 0,0:09:56.00,0:09:59.00,Default,,0000,0000,0000,,what word, or what entity, you know, in a social network that they are,
Dialogue: 0,0:09:59.00,0:10:03.00,Default,,0000,0000,0000,,and then the arcs would show who is directly connected to whom.
Dialogue: 0,0:10:03.00,0:10:06.00,Default,,0000,0000,0000,,And so one way to manage that, right, is just to have two independent collections - a collection
Dialogue: 0,0:10:06.00,0:10:08.00,Default,,0000,0000,0000,,of nodes and a
Dialogue: 0,0:10:08.00,0:10:11.00,Default,,0000,0000,0000,,collection of arcs, and that when I need to know things about connections, I'll have to, kind of, use both
Dialogue: 0,0:10:11.00,0:10:12.00,Default,,0000,0000,0000,,in tandem.
Dialogue: 0,0:10:12.00,0:10:14.00,Default,,0000,0000,0000,,So if I want to know if A is connected to B,
Dialogue: 0,0:10:14.00,0:10:18.00,Default,,0000,0000,0000,,I might actually have to just walk through the entire set of arcs trying to find
Dialogue: 0,0:10:18.00,0:10:22.00,Default,,0000,0000,0000,,one that connects A and B as its endpoints. If I want to see if
Dialogue: 0,0:10:22.00,0:10:25.00,Default,,0000,0000,0000,,C is connected to B, same thing, just walk down the whole set.
Dialogue: 0,0:10:25.00,0:10:27.00,Default,,0000,0000,0000,,
Dialogue: 0,0:10:27.00,0:10:29.00,Default,,0000,0000,0000,,
Dialogue: 0,0:10:29.00,0:10:31.00,Default,,0000,0000,0000,,That's probably the simplest thing to do, right, is to just, kind of,
Dialogue: 0,0:10:31.00,0:10:35.00,Default,,0000,0000,0000,,have them just be maintained as the two things that are used in conjunction.
Dialogue: 0,0:10:35.00,0:10:37.00,Default,,0000,0000,0000,,More likely, what you're gonna want to do
Dialogue: 0,0:10:37.00,0:10:39.00,Default,,0000,0000,0000,,is provide some access that
Dialogue: 0,0:10:39.00,0:10:42.00,Default,,0000,0000,0000,,when at a current node, you're currently trying to do some processing
Dialogue: 0,0:10:42.00,0:10:47.00,Default,,0000,0000,0000,,from the Node B, it would be convenient if you could easily access those nodes
Dialogue: 0,0:10:47.00,0:10:51.00,Default,,0000,0000,0000,,that emanate or outgo from the B node. That's typically the thing you're trying
Dialogue: 0,0:10:51.00,0:10:52.00,Default,,0000,0000,0000,,to do is
Dialogue: 0,0:10:52.00,0:10:55.00,Default,,0000,0000,0000,,at B try to visit its neighbors,
Dialogue: 0,0:10:55.00,0:10:58.00,Default,,0000,0000,0000,,and rather that having to, kind of, pluck them out of the entire collection,
Dialogue: 0,0:10:58.00,0:11:01.00,Default,,0000,0000,0000,,it might be handy if they were already, kind of, stored in such a way to make it
Dialogue: 0,0:11:01.00,0:11:03.00,Default,,0000,0000,0000,,easy for you to get to that.
Dialogue: 0,0:11:03.00,0:11:06.00,Default,,0000,0000,0000,,So the two ways that try to represent adjacency
Dialogue: 0,0:11:06.00,0:11:10.00,Default,,0000,0000,0000,,in a more efficient way are the adjacency list and the adjacency matrix.
Dialogue: 0,0:11:10.00,0:11:14.00,Default,,0000,0000,0000,,So in an adjacency list representation, we have a way of associating with each node,
Dialogue: 0,0:11:14.00,0:11:17.00,Default,,0000,0000,0000,,probably just by storing it in the node structure itself,
Dialogue: 0,0:11:17.00,0:11:21.00,Default,,0000,0000,0000,,those arcs that outgo from there. So, in this case, A has as direct
Dialogue: 0,0:11:21.00,0:11:22.00,Default,,0000,0000,0000,,connection to the B
Dialogue: 0,0:11:22.00,0:11:23.00,Default,,0000,0000,0000,,and C Nodes,
Dialogue: 0,0:11:23.00,0:11:26.00,Default,,0000,0000,0000,,and so I would have that information stored with the A Node, which is my
Dialogue: 0,0:11:26.00,0:11:29.00,Default,,0000,0000,0000,,vector or set of outgoing connections.
Dialogue: 0,0:11:29.00,0:11:33.00,Default,,0000,0000,0000,,Similarly, B has one outgoing connection, which goes to D. C has an outgoing connection to D, and
Dialogue: 0,0:11:33.00,0:11:37.00,Default,,0000,0000,0000,,then D has outgoing connections that lead back to A and
Dialogue: 0,0:11:37.00,0:11:40.00,Default,,0000,0000,0000,,to B. So at a particular node I could say, well, who's my neighbors?
Dialogue: 0,0:11:40.00,0:11:41.00,Default,,0000,0000,0000,,It would be
Dialogue: 0,0:11:41.00,0:11:46.00,Default,,0000,0000,0000,,easily accessible and not have to be retrieved, or searched, or filtered.
Dialogue: 0,0:11:46.00,0:11:48.00,Default,,0000,0000,0000,,Another way of doing that
Dialogue: 0,0:11:48.00,0:11:51.00,Default,,0000,0000,0000,,is to realize that, in a sense, what we have is this, kind of,
Dialogue: 0,0:11:51.00,0:11:53.00,Default,,0000,0000,0000,,end by end grid
Dialogue: 0,0:11:53.00,0:11:56.00,Default,,0000,0000,0000,,where each node is potentially connected to
Dialogue: 0,0:11:56.00,0:12:00.00,Default,,0000,0000,0000,,the other N -1 nodes in that graph. And so if I just build
Dialogue: 0,0:12:00.00,0:12:03.00,Default,,0000,0000,0000,,a 2x2 matrix that's labeled with
Dialogue: 0,0:12:03.00,0:12:06.00,Default,,0000,0000,0000,,all the node names on this side and all the node names across the top, that the
Dialogue: 0,0:12:06.00,0:12:08.00,Default,,0000,0000,0000,,intersection of this says
Dialogue: 0,0:12:08.00,0:12:11.00,Default,,0000,0000,0000,,is there an arc that leads away from A and
Dialogue: 0,0:12:11.00,0:12:14.00,Default,,0000,0000,0000,,ends at B? Yes, there is. Is there one from A to C?
Dialogue: 0,0:12:14.00,0:12:18.00,Default,,0000,0000,0000,,And in the places where there is not an existing connection, a self loop or
Dialogue: 0,0:12:18.00,0:12:19.00,Default,,0000,0000,0000,,
Dialogue: 0,0:12:19.00,0:12:23.00,Default,,0000,0000,0000,,just a connection that doesn't exist, right, I have an empty slot. So maybe these would be Booleans
Dialogue: 0,0:12:23.00,0:12:25.00,Default,,0000,0000,0000,,true and false or something, or maybe there'd be some more information here
Dialogue: 0,0:12:25.00,0:12:27.00,Default,,0000,0000,0000,,about the distance
Dialogue: 0,0:12:27.00,0:12:30.00,Default,,0000,0000,0000,,or other associated arc properties for that
Dialogue: 0,0:12:30.00,0:12:31.00,Default,,0000,0000,0000,,particular connection.
Dialogue: 0,0:12:31.00,0:12:34.00,Default,,0000,0000,0000,,In this case, it's actually very easy then to actually do the really quick
Dialogue: 0,0:12:34.00,0:12:35.00,Default,,0000,0000,0000,,search of
Dialogue: 0,0:12:35.00,0:12:38.00,Default,,0000,0000,0000,,I'm at A and I want to know if I can get to B, then it's really just a
Dialogue: 0,0:12:38.00,0:12:41.00,Default,,0000,0000,0000,,matter of reaching right into the
Dialogue: 0,0:12:41.00,0:12:45.00,Default,,0000,0000,0000,,slot in constant time in that matrix to pull it out, and
Dialogue: 0,0:12:45.00,0:12:47.00,Default,,0000,0000,0000,,so
Dialogue: 0,0:12:47.00,0:12:49.00,Default,,0000,0000,0000,,this one involves a lot of searching to find things. This one involves, perhaps, a
Dialogue: 0,0:12:49.00,0:12:52.00,Default,,0000,0000,0000,,little bit of searching. If I want to know if A is connected to B, I might have to look
Dialogue: 0,0:12:52.00,0:12:55.00,Default,,0000,0000,0000,,through all its outgoing connections, right? This one gives me that direct
Dialogue: 0,0:12:55.00,0:12:56.00,Default,,0000,0000,0000,,access,
Dialogue: 0,0:12:56.00,0:13:00.00,Default,,0000,0000,0000,,but the tradeoffs here has to do with where the space starts building up, right?
Dialogue: 0,0:13:00.00,0:13:03.00,Default,,0000,0000,0000,,A full NxN matrix could be very big,
Dialogue: 0,0:13:03.00,0:13:06.00,Default,,0000,0000,0000,,and sometimes we're allocating space as though there are a full set of
Dialogue: 0,0:13:06.00,0:13:09.00,Default,,0000,0000,0000,,connections between all the nodes, every node connected to every other,
Dialogue: 0,0:13:09.00,0:13:12.00,Default,,0000,0000,0000,,and in the cases where a lot of those things are false, there's a lot of
Dialogue: 0,0:13:12.00,0:13:13.00,Default,,0000,0000,0000,,capacity
Dialogue: 0,0:13:13.00,0:13:16.00,Default,,0000,0000,0000,,that we have set aside that we're not really tapping into.
Dialogue: 0,0:13:16.00,0:13:19.00,Default,,0000,0000,0000,,And so in the case of a graph that we call dense,
Dialogue: 0,0:13:19.00,0:13:23.00,Default,,0000,0000,0000,,where there's a lot of connections, it will use a lot of that capacity, and it might make sense
Dialogue: 0,0:13:23.00,0:13:27.00,Default,,0000,0000,0000,,in a graph that's more sparse, where there's a few connections. So you have
Dialogue: 0,0:13:27.00,0:13:31.00,Default,,0000,0000,0000,,thousands of nodes, but maybe only three or four on average are connected to one.
Dialogue: 0,0:13:31.00,0:13:35.00,Default,,0000,0000,0000,,Then having allocated 1,000 slots of which to only fill in three
Dialogue: 0,0:13:35.00,0:13:36.00,Default,,0000,0000,0000,,might become
Dialogue: 0,0:13:36.00,0:13:40.00,Default,,0000,0000,0000,,rather space inefficient. You might prefer an adjacency list representation that
Dialogue: 0,0:13:40.00,0:13:41.00,Default,,0000,0000,0000,,can get you
Dialogue: 0,0:13:41.00,0:13:44.00,Default,,0000,0000,0000,,to the ones you're actually using versus the other,
Dialogue: 0,0:13:44.00,0:13:47.00,Default,,0000,0000,0000,,but in terms of the adjacency matrices is very fast,
Dialogue: 0,0:13:47.00,0:13:48.00,Default,,0000,0000,0000,,right? A lot of space thrown at this
Dialogue: 0,0:13:48.00,0:13:51.00,Default,,0000,0000,0000,,gives you this immediate 0,1 access to know
Dialogue: 0,0:13:51.00,0:13:55.00,Default,,0000,0000,0000,,who your neighbors are. So
Dialogue: 0,0:13:55.00,0:13:59.00,Default,,0000,0000,0000,,we're gonna use the adjacency list, kind of, strategy here
Dialogue: 0,0:13:59.00,0:14:02.00,Default,,0000,0000,0000,,for the code we're gonna do today, and it's, kind
Dialogue: 0,0:14:02.00,0:14:07.00,Default,,0000,0000,0000,,of, a good compromise between the two alternatives that we've seen there.
Dialogue: 0,0:14:07.00,0:14:08.00,Default,,0000,0000,0000,,So I have a struct node.
Dialogue: 0,0:14:08.00,0:14:11.00,Default,,0000,0000,0000,,It has some information for the node. Given that I'm not being very specific
Dialogue: 0,0:14:11.00,0:14:14.00,Default,,0000,0000,0000,,about what the graph is, I'm just gonna, kind of, leave that unspecified. It might be that it's
Dialogue: 0,0:14:14.00,0:14:17.00,Default,,0000,0000,0000,,the city name. It might be that it's a word. It might be that it's a person in a
Dialogue: 0,0:14:17.00,0:14:19.00,Default,,0000,0000,0000,,social network, you know,
Dialogue: 0,0:14:19.00,0:14:23.00,Default,,0000,0000,0000,,some information that represents what this node is an entity,
Dialogue: 0,0:14:23.00,0:14:28.00,Default,,0000,0000,0000,,and then there's gonna be a set of arcs or a set of nodes it's connected to,
Dialogue: 0,0:14:28.00,0:14:32.00,Default,,0000,0000,0000,,and so I'm using vector here. I could be using set. I could be using a
Dialogue: 0,0:14:32.00,0:14:35.00,Default,,0000,0000,0000,,raw array, or a link list, or any of these things.
Dialogue: 0,0:14:35.00,0:14:38.00,Default,,0000,0000,0000,,I need to use some unbounded collection though because there's no guarantee that
Dialogue: 0,0:14:38.00,0:14:42.00,Default,,0000,0000,0000,,they will be 0, or 1, or 2 the way there is in a link list or a tree where there's a
Dialogue: 0,0:14:42.00,0:14:45.00,Default,,0000,0000,0000,,specified number of outgoing links. There can be any number of them, so I'm just leaving
Dialogue: 0,0:14:45.00,0:14:46.00,Default,,0000,0000,0000,,
Dialogue: 0,0:14:46.00,0:14:47.00,Default,,0000,0000,0000,,a
Dialogue: 0,0:14:47.00,0:14:51.00,Default,,0000,0000,0000,,variable size collection here to do that work for me.
Dialogue: 0,0:14:51.00,0:14:52.00,Default,,0000,0000,0000,,The graph itself,
Dialogue: 0,0:14:52.00,0:14:55.00,Default,,0000,0000,0000,,so I have this idea of all the nodes in the graph, right, would each get a new
Dialogue: 0,0:14:55.00,0:14:58.00,Default,,0000,0000,0000,,node structure and then be wired up to the other nodes that they are connected
Dialogue: 0,0:14:58.00,0:15:00.00,Default,,0000,0000,0000,,to,
Dialogue: 0,0:15:00.00,0:15:02.00,Default,,0000,0000,0000,,but then when I'm trying to operate on that graph,
Dialogue: 0,0:15:02.00,0:15:06.00,Default,,0000,0000,0000,,I can't just take one pointer and say here's a pointer to some node in the
Dialogue: 0,0:15:06.00,0:15:09.00,Default,,0000,0000,0000,,graph and say this is - and from here you have accessed everything. In the way
Dialogue: 0,0:15:09.00,0:15:11.00,Default,,0000,0000,0000,,that a tree,
Dialogue: 0,0:15:11.00,0:15:13.00,Default,,0000,0000,0000,,the only thing we need to keep track of is the pointer to the root,
Dialogue: 0,0:15:13.00,0:15:17.00,Default,,0000,0000,0000,,or a link list, the only thing we keep a pointer to, typically, is that frontmost
Dialogue: 0,0:15:17.00,0:15:19.00,Default,,0000,0000,0000,,cell, and from there, we can reach everything else.
Dialogue: 0,0:15:19.00,0:15:23.00,Default,,0000,0000,0000,,There is no special head or root cell in a graph.
Dialogue: 0,0:15:23.00,0:15:27.00,Default,,0000,0000,0000,,A graph is this
Dialogue: 0,0:15:27.00,0:15:30.00,Default,,0000,0000,0000,,being, kind of, a crazy collection without a lot of rules about
Dialogue: 0,0:15:30.00,0:15:35.00,Default,,0000,0000,0000,,how they are connected. In fact, it's not even guaranteed that they totally are
Dialogue: 0,0:15:35.00,0:15:36.00,Default,,0000,0000,0000,,connected.
Dialogue: 0,0:15:36.00,0:15:38.00,Default,,0000,0000,0000,,That I can't
Dialogue: 0,0:15:38.00,0:15:41.00,Default,,0000,0000,0000,,guarantee that if I had a pointer, for example, to C,
Dialogue: 0,0:15:41.00,0:15:44.00,Default,,0000,0000,0000,,right, I may or may not be able to reach all the nodes from there.
Dialogue: 0,0:15:44.00,0:15:49.00,Default,,0000,0000,0000,,If I had a pointer to A, right, A can get to C and B, and then also
Dialogue: 0,0:15:49.00,0:15:52.00,Default,,0000,0000,0000,,down to D, but, for example, there could just be an E node over here that was only
Dialogue: 0,0:15:52.00,0:15:55.00,Default,,0000,0000,0000,,connected to C or not connected to anything at all for that matter, connected
Dialogue: 0,0:15:55.00,0:15:57.00,Default,,0000,0000,0000,,to F in their own little island.
Dialogue: 0,0:15:57.00,0:16:01.00,Default,,0000,0000,0000,,That there is no way to identify some special node from which you could reach
Dialogue: 0,0:16:01.00,0:16:02.00,Default,,0000,0000,0000,,all the nodes.
Dialogue: 0,0:16:02.00,0:16:04.00,Default,,0000,0000,0000,,There isn't a special root node,
Dialogue: 0,0:16:04.00,0:16:07.00,Default,,0000,0000,0000,,and you can't even just arbitrarily pick one to be the root because actually there's no
Dialogue: 0,0:16:07.00,0:16:10.00,Default,,0000,0000,0000,,guarantee that it will be connected to all of the others. So it would not give you
Dialogue: 0,0:16:10.00,0:16:13.00,Default,,0000,0000,0000,,access to the full entirety of your graph if you just picked on and said I want anything
Dialogue: 0,0:16:13.00,0:16:16.00,Default,,0000,0000,0000,,reachable from here, it might not get you the whole thing. So,
Dialogue: 0,0:16:16.00,0:16:18.00,Default,,0000,0000,0000,,typically, what you need to really operate on is
Dialogue: 0,0:16:18.00,0:16:21.00,Default,,0000,0000,0000,,the entire collection of node stars. You'll have a set or a vector
Dialogue: 0,0:16:21.00,0:16:24.00,Default,,0000,0000,0000,,that contains all of the nodes that are in the graph,
Dialogue: 0,0:16:24.00,0:16:26.00,Default,,0000,0000,0000,,and then within that, there's a bunch of other connections that are
Dialogue: 0,0:16:26.00,0:16:35.00,Default,,0000,0000,0000,,being made on the graph connectivity that you're also exploring.
Dialogue: 0,0:16:35.00,0:16:37.00,Default,,0000,0000,0000,,So let's make it a little bit more concrete
Dialogue: 0,0:16:37.00,0:16:39.00,Default,,0000,0000,0000,,
Dialogue: 0,0:16:39.00,0:16:40.00,Default,,0000,0000,0000,,and talk a little bit about
Dialogue: 0,0:16:40.00,0:16:43.00,Default,,0000,0000,0000,,what really is a node; what really is an arc?
Dialogue: 0,0:16:43.00,0:16:46.00,Default,,0000,0000,0000,,There may be, actually, be some more information I need to store than just a
Dialogue: 0,0:16:46.00,0:16:48.00,Default,,0000,0000,0000,,node is connected to other nodes.
Dialogue: 0,0:16:48.00,0:16:51.00,Default,,0000,0000,0000,,So in the case of a list or a tree,
Dialogue: 0,0:16:51.00,0:16:54.00,Default,,0000,0000,0000,,the next field and the left and the right field are really just pointers for the
Dialogue: 0,0:16:54.00,0:16:56.00,Default,,0000,0000,0000,,purpose of organization.
Dialogue: 0,0:16:56.00,0:16:58.00,Default,,0000,0000,0000,,That's the pointer to the next cell.
Dialogue: 0,0:16:58.00,0:17:02.00,Default,,0000,0000,0000,,There's no data that is really associated with that link itself.
Dialogue: 0,0:17:02.00,0:17:05.00,Default,,0000,0000,0000,,That's not true in the case of a graph.
Dialogue: 0,0:17:05.00,0:17:09.00,Default,,0000,0000,0000,,That often what the links that connect up the nodes
Dialogue: 0,0:17:09.00,0:17:12.00,Default,,0000,0000,0000,,actually do have a real role to play in terms of being data.
Dialogue: 0,0:17:12.00,0:17:14.00,Default,,0000,0000,0000,,It may be that what they tell you is
Dialogue: 0,0:17:14.00,0:17:18.00,Default,,0000,0000,0000,,what road you're taking here, or how long this path is, or how much this
Dialogue: 0,0:17:18.00,0:17:22.00,Default,,0000,0000,0000,,flight costs, or what time this flight leaves, or how full this flight already is,
Dialogue: 0,0:17:22.00,0:17:24.00,Default,,0000,0000,0000,,or who knows, you know, just other information
Dialogue: 0,0:17:24.00,0:17:27.00,Default,,0000,0000,0000,,that is more than just this nodes connected to that one. It's, like, how is it
Dialogue: 0,0:17:27.00,0:17:30.00,Default,,0000,0000,0000,,connected; what is it connected by, and what are the details of how that
Dialogue: 0,0:17:30.00,0:17:31.00,Default,,0000,0000,0000,,connection
Dialogue: 0,0:17:31.00,0:17:32.00,Default,,0000,0000,0000,,
Dialogue: 0,0:17:32.00,0:17:34.00,Default,,0000,0000,0000,,is being represented?
Dialogue: 0,0:17:34.00,0:17:38.00,Default,,0000,0000,0000,,So it's likely that what you really want is not just pointers to other nodes but
Dialogue: 0,0:17:38.00,0:17:42.00,Default,,0000,0000,0000,,information about that actual link stored with an arc structure.
Dialogue: 0,0:17:42.00,0:17:44.00,Default,,0000,0000,0000,,So, typically, we're gonna have
Dialogue: 0,0:17:44.00,0:17:45.00,Default,,0000,0000,0000,,an arc
Dialogue: 0,0:17:45.00,0:17:48.00,Default,,0000,0000,0000,,which has information about that arc, how long, how much it costs, you know,
Dialogue: 0,0:17:48.00,0:17:50.00,Default,,0000,0000,0000,,what flight number it is,
Dialogue: 0,0:17:50.00,0:17:52.00,Default,,0000,0000,0000,,that will have pointers to the start and end node that it is connecting.
Dialogue: 0,0:17:52.00,0:17:54.00,Default,,0000,0000,0000,,The node
Dialogue: 0,0:17:54.00,0:17:57.00,Default,,0000,0000,0000,,then has a collection of arcs,
Dialogue: 0,0:17:57.00,0:18:00.00,Default,,0000,0000,0000,,and those arcs are expected to, in the adjacency list form, will all be arcs
Dialogue: 0,0:18:00.00,0:18:02.00,Default,,0000,0000,0000,,that start at this node.
Dialogue: 0,0:18:02.00,0:18:05.00,Default,,0000,0000,0000,,So their start node is equal to the one that's holding onto to them, and then
Dialogue: 0,0:18:05.00,0:18:06.00,Default,,0000,0000,0000,,they have an end
Dialogue: 0,0:18:06.00,0:18:10.00,Default,,0000,0000,0000,,pointer that points to the node at the other end of the arc. Well,
Dialogue: 0,0:18:10.00,0:18:13.00,Default,,0000,0000,0000,,this gets us into a little C++ bind
Dialogue: 0,0:18:13.00,0:18:16.00,Default,,0000,0000,0000,,because I've described these data structures
Dialogue: 0,0:18:16.00,0:18:17.00,Default,,0000,0000,0000,,in a way
Dialogue: 0,0:18:17.00,0:18:22.00,Default,,0000,0000,0000,,that they both depend on each other; that an arc has pointers to the start and the end
Dialogue: 0,0:18:22.00,0:18:22.00,Default,,0000,0000,0000,,node.
Dialogue: 0,0:18:22.00,0:18:27.00,Default,,0000,0000,0000,,A node has a collection of arcs, which is probably a vector or a set of arc pointers,
Dialogue: 0,0:18:27.00,0:18:28.00,Default,,0000,0000,0000,,and so
Dialogue: 0,0:18:28.00,0:18:31.00,Default,,0000,0000,0000,,I'm starting to define the structure for arc,
Dialogue: 0,0:18:31.00,0:18:33.00,Default,,0000,0000,0000,,and then I want to talk about node in it,
Dialogue: 0,0:18:33.00,0:18:35.00,Default,,0000,0000,0000,,and I think, oh, okay, well, then I better define node first because C++ always likes to
Dialogue: 0,0:18:35.00,0:18:38.00,Default,,0000,0000,0000,,see things in order. Remember, it always wants to see A,
Dialogue: 0,0:18:38.00,0:18:42.00,Default,,0000,0000,0000,,and then B if B uses A, and so in terms of how your functions and data
Dialogue: 0,0:18:42.00,0:18:45.00,Default,,0000,0000,0000,,structures work, you've always gotten this idea like, well, go do the one first. Well, if I say,
Dialogue: 0,0:18:45.00,0:18:48.00,Default,,0000,0000,0000,,okay, arc's gonna need node. I start to write arc, and I say, oh, I
Dialogue: 0,0:18:48.00,0:18:50.00,Default,,0000,0000,0000,,need to talk about node. Well, I better put node up here,
Dialogue: 0,0:18:50.00,0:18:54.00,Default,,0000,0000,0000,,right? But then when I'm starting to write node, I start talking about arc, and they have a
Dialogue: 0,0:18:54.00,0:18:57.00,Default,,0000,0000,0000,,circular reference to each other, right? They both
Dialogue: 0,0:18:57.00,0:19:00.00,Default,,0000,0000,0000,,want to depend on the other one before we've gotten around to telling the
Dialogue: 0,0:19:00.00,0:19:01.00,Default,,0000,0000,0000,,compiler about it.
Dialogue: 0,0:19:01.00,0:19:04.00,Default,,0000,0000,0000,,One of them has to go first, right? What are we gonna do?
Dialogue: 0,0:19:04.00,0:19:08.00,Default,,0000,0000,0000,,What we need to do is use the C++ forward reference
Dialogue: 0,0:19:08.00,0:19:09.00,Default,,0000,0000,0000,,as a
Dialogue: 0,0:19:09.00,0:19:12.00,Default,,0000,0000,0000,,little hint to the compiler
Dialogue: 0,0:19:12.00,0:19:13.00,Default,,0000,0000,0000,,that
Dialogue: 0,0:19:13.00,0:19:17.00,Default,,0000,0000,0000,,we are gonna be defining a Node T structure in a little bit;
Dialogue: 0,0:19:17.00,0:19:18.00,Default,,0000,0000,0000,,we're gonna get to it,
Dialogue: 0,0:19:18.00,0:19:22.00,Default,,0000,0000,0000,,but first we're gonna define the Arc T structure that uses that Node T, and then
Dialogue: 0,0:19:22.00,0:19:25.00,Default,,0000,0000,0000,,we're gonna get around to it. So we're gonna give it, like, a little heads up that says
Dialogue: 0,0:19:25.00,0:19:29.00,Default,,0000,0000,0000,,there later will be an Act 2 of this play. We're gonna introduce a
Dialogue: 0,0:19:29.00,0:19:31.00,Default,,0000,0000,0000,,character called Node T.
Dialogue: 0,0:19:31.00,0:19:33.00,Default,,0000,0000,0000,,So you can now
Dialogue: 0,0:19:33.00,0:19:34.00,Default,,0000,0000,0000,,start talking about Node
Dialogue: 0,0:19:34.00,0:19:37.00,Default,,0000,0000,0000,,T in some simple ways
Dialogue: 0,0:19:37.00,0:19:40.00,Default,,0000,0000,0000,,based on your agreement to the compiler that you plan on telling it more
Dialogue: 0,0:19:40.00,0:19:41.00,Default,,0000,0000,0000,,about Node T later.
Dialogue: 0,0:19:41.00,0:19:45.00,Default,,0000,0000,0000,,So the struct Node T says there will be a struct called Node T.
Dialogue: 0,0:19:45.00,0:19:47.00,Default,,0000,0000,0000,,Okay, the compiler says, okay, I'll write that down.
Dialogue: 0,0:19:47.00,0:19:51.00,Default,,0000,0000,0000,,You start defining struct Arc T, and it says, oh, I see you have these pointers
Dialogue: 0,0:19:51.00,0:19:54.00,Default,,0000,0000,0000,,to the node T. Okay. Well, you told me there'd be a struct like that; I guess that'll work out.
Dialogue: 0,0:19:54.00,0:19:58.00,Default,,0000,0000,0000,,And now you told it what struct Node T is. It's, like, oh, I have a vector
Dialogue: 0,0:19:58.00,0:19:59.00,Default,,0000,0000,0000,,with these pointers to arc,
Dialogue: 0,0:19:59.00,0:20:02.00,Default,,0000,0000,0000,,and then it says, okay, now I see the whole picture, and
Dialogue: 0,0:20:02.00,0:20:03.00,Default,,0000,0000,0000,,it all worked out.
Dialogue: 0,0:20:03.00,0:20:08.00,Default,,0000,0000,0000,,So it's just a little bit of a
Dialogue: 0,0:20:08.00,0:20:11.00,Default,,0000,0000,0000,,requirement of how the C++ compiler likes to see stuff in order without ever having
Dialogue: 0,0:20:11.00,0:20:16.00,Default,,0000,0000,0000,,to go backwards to check anything out again. Okay. So
Dialogue: 0,0:20:16.00,0:20:19.00,Default,,0000,0000,0000,,I got myself some node structures, got
Dialogue: 0,0:20:19.00,0:20:21.00,Default,,0000,0000,0000,,some arc structures; they're all
Dialogue: 0,0:20:21.00,0:20:22.00,Default,,0000,0000,0000,,working together.
Dialogue: 0,0:20:22.00,0:20:24.00,Default,,0000,0000,0000,,I'm gonna try to do some traversals.
Dialogue: 0,0:20:24.00,0:20:26.00,Default,,0000,0000,0000,,Try to do some operations that
Dialogue: 0,0:20:26.00,0:20:29.00,Default,,0000,0000,0000,,work their way around the graph.
Dialogue: 0,0:20:29.00,0:20:30.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:20:30.00,0:20:33.00,Default,,0000,0000,0000,,tree traversals, right, the pre, and post, and in order
Dialogue: 0,0:20:33.00,0:20:36.00,Default,,0000,0000,0000,,are ways that you start at the root, and you visit all the nodes on the tree,
Dialogue: 0,0:20:36.00,0:20:40.00,Default,,0000,0000,0000,,a very common need to, kind of, process, to delete nodes,
Dialogue: 0,0:20:40.00,0:20:43.00,Default,,0000,0000,0000,,to print the nodes, to whatnot. So we might want to do the same thing on graphs. I've got a
Dialogue: 0,0:20:43.00,0:20:47.00,Default,,0000,0000,0000,,graph out there, and I'd like to go exploring it. Maybe I just want to print, and if
Dialogue: 0,0:20:47.00,0:20:50.00,Default,,0000,0000,0000,,I'm in the Gates building, what are all the places that I can reach from
Dialogue: 0,0:20:50.00,0:20:53.00,Default,,0000,0000,0000,,the Gates building? Where can I go to; what
Dialogue: 0,0:20:53.00,0:20:54.00,Default,,0000,0000,0000,,options do I have?
Dialogue: 0,0:20:54.00,0:20:57.00,Default,,0000,0000,0000,,What I'm gonna do is a traversal
Dialogue: 0,0:20:57.00,0:21:01.00,Default,,0000,0000,0000,,starting at a node and, kind of, working my way outward to the visible, reachable
Dialogue: 0,0:21:01.00,0:21:04.00,Default,,0000,0000,0000,,nodes that I can follow those paths to get there.
Dialogue: 0,0:21:04.00,0:21:07.00,Default,,0000,0000,0000,,We're gonna look at two different ways to do this.
Dialogue: 0,0:21:07.00,0:21:09.00,Default,,0000,0000,0000,,One is Depth-first and one is Breadth-first,
Dialogue: 0,0:21:09.00,0:21:13.00,Default,,0000,0000,0000,,and I'll show you both algorithms, and they
Dialogue: 0,0:21:13.00,0:21:15.00,Default,,0000,0000,0000,,will visit the same nodes;
Dialogue: 0,0:21:15.00,0:21:19.00,Default,,0000,0000,0000,,when all is done and said, they will visit all the reachable nodes starting from a
Dialogue: 0,0:21:19.00,0:21:20.00,Default,,0000,0000,0000,,position,
Dialogue: 0,0:21:20.00,0:21:21.00,Default,,0000,0000,0000,,but they will visit them in different order.
Dialogue: 0,0:21:21.00,0:21:25.00,Default,,0000,0000,0000,,So just like the pre/post in order tree traversals, they visit all the same
Dialogue: 0,0:21:25.00,0:21:28.00,Default,,0000,0000,0000,,notes. It's just a matter of when they get around to doing it
Dialogue: 0,0:21:28.00,0:21:29.00,Default,,0000,0000,0000,,is how
Dialogue: 0,0:21:29.00,0:21:32.00,Default,,0000,0000,0000,,we distinguish depth and breadth-first traversals.
Dialogue: 0,0:21:32.00,0:21:34.00,Default,,0000,0000,0000,,Because we have this graph structure
Dialogue: 0,0:21:34.00,0:21:40.00,Default,,0000,0000,0000,,that has this loose connectivity and the possibility of cycles and multiple paths
Dialogue: 0,0:21:40.00,0:21:41.00,Default,,0000,0000,0000,,to the same node,
Dialogue: 0,0:21:41.00,0:21:44.00,Default,,0000,0000,0000,,we are gonna have to be a little bit careful at how we do our work to make
Dialogue: 0,0:21:44.00,0:21:48.00,Default,,0000,0000,0000,,sure that we don't end up getting stuck in some infinite loop when we keep
Dialogue: 0,0:21:48.00,0:21:51.00,Default,,0000,0000,0000,,going around the ABC cycle in a particular graph.
Dialogue: 0,0:21:51.00,0:21:55.00,Default,,0000,0000,0000,,That we need to realize when we're revisiting something we've seen before,
Dialogue: 0,0:21:55.00,0:21:56.00,Default,,0000,0000,0000,,and then not
Dialogue: 0,0:21:56.00,0:21:57.00,Default,,0000,0000,0000,,
Dialogue: 0,0:21:57.00,0:21:59.00,Default,,0000,0000,0000,,trigger, kind of, an
Dialogue: 0,0:21:59.00,0:22:03.00,Default,,0000,0000,0000,,exploration we've already done.
Dialogue: 0,0:22:03.00,0:22:06.00,Default,,0000,0000,0000,,So let's look at depth-first first.
Dialogue: 0,0:22:06.00,0:22:09.00,Default,,0000,0000,0000,,This is probably the simpler of the two. They're both, actually, pretty simple.
Dialogue: 0,0:22:09.00,0:22:13.00,Default,,0000,0000,0000,,Depth-first traversal uses recursion to do its work,
Dialogue: 0,0:22:13.00,0:22:18.00,Default,,0000,0000,0000,,and the idea is that you pick a starting node - let's say I want to start at Gates,
Dialogue: 0,0:22:18.00,0:22:21.00,Default,,0000,0000,0000,,and that maybe what I'm trying to find is all the reachable nodes from Gates.
Dialogue: 0,0:22:21.00,0:22:24.00,Default,,0000,0000,0000,,If I don't have a starting node, then I can just pick one arbitrarily from the
Dialogue: 0,0:22:24.00,0:22:27.00,Default,,0000,0000,0000,,graph because there is actually no root node of special status,
Dialogue: 0,0:22:27.00,0:22:30.00,Default,,0000,0000,0000,,and the idea is to go deep. That
Dialogue: 0,0:22:30.00,0:22:33.00,Default,,0000,0000,0000,,in the case of, for example, a maze, it might be that I
Dialogue: 0,0:22:33.00,0:22:36.00,Default,,0000,0000,0000,,choose to go north, and then I just keep going north. I just go north, north, north, north, north until
Dialogue: 0,0:22:36.00,0:22:40.00,Default,,0000,0000,0000,,I run into a dead wall, and then I say, oh, I have to go east, and I go east, east, east, east, east. The idea is to
Dialogue: 0,0:22:40.00,0:22:42.00,Default,,0000,0000,0000,,just go as far away from
Dialogue: 0,0:22:42.00,0:22:46.00,Default,,0000,0000,0000,,the original state as I can, just keep going outward, outward, outward, outward,
Dialogue: 0,0:22:46.00,0:22:47.00,Default,,0000,0000,0000,,outward, outward, outward,
Dialogue: 0,0:22:47.00,0:22:50.00,Default,,0000,0000,0000,,and eventually I'm gonna run into some dead end, and that dead end could be I
Dialogue: 0,0:22:50.00,0:22:52.00,Default,,0000,0000,0000,,get to a node that has no outgoing arcs,
Dialogue: 0,0:22:52.00,0:22:54.00,Default,,0000,0000,0000,,or it could be that I get to a node
Dialogue: 0,0:22:54.00,0:22:57.00,Default,,0000,0000,0000,,that whose only arcs come back to places I've already been,
Dialogue: 0,0:22:57.00,0:22:58.00,Default,,0000,0000,0000,,so it cycles back on itself, in
Dialogue: 0,0:22:58.00,0:23:01.00,Default,,0000,0000,0000,,which case, that also is really a dead end.
Dialogue: 0,0:23:01.00,0:23:03.00,Default,,0000,0000,0000,,So you go deep.
Dialogue: 0,0:23:03.00,0:23:06.00,Default,,0000,0000,0000,,You go north, and you see as far as you can get, and
Dialogue: 0,0:23:06.00,0:23:10.00,Default,,0000,0000,0000,,only after you've, kind of, fully explored everything reachable from starting in
Dialogue: 0,0:23:10.00,0:23:11.00,Default,,0000,0000,0000,,the north direction
Dialogue: 0,0:23:11.00,0:23:13.00,Default,,0000,0000,0000,,do you backtrack,
Dialogue: 0,0:23:13.00,0:23:16.00,Default,,0000,0000,0000,,unmake that decision, and say, well, how about not north; how about east, right? And then
Dialogue: 0,0:23:16.00,0:23:19.00,Default,,0000,0000,0000,,find everything you can get to from the east, and
Dialogue: 0,0:23:19.00,0:23:22.00,Default,,0000,0000,0000,,after, kind of, going all through that, come back and try south, and so on. So all of the
Dialogue: 0,0:23:22.00,0:23:23.00,Default,,0000,0000,0000,,options you have
Dialogue: 0,0:23:23.00,0:23:26.00,Default,,0000,0000,0000,,exhaustively getting through all your
Dialogue: 0,0:23:26.00,0:23:26.00,Default,,0000,0000,0000,,neighbors
Dialogue: 0,0:23:26.00,0:23:29.00,Default,,0000,0000,0000,,in this, kind of, go-deep strategy. Well,
Dialogue: 0,0:23:29.00,0:23:32.00,Default,,0000,0000,0000,,the important thing is you realize if you've got this recursion going, so what
Dialogue: 0,0:23:32.00,0:23:35.00,Default,,0000,0000,0000,,you're actually doing, basically, is saying I'm gonna step to my neighbor to the
Dialogue: 0,0:23:35.00,0:23:40.00,Default,,0000,0000,0000,,right, and I'm gonna explore all the things, so do a depth-first search from there
Dialogue: 0,0:23:40.00,0:23:43.00,Default,,0000,0000,0000,,to find all the places you can reach, and that one says, well, I'm gonna step through this spot
Dialogue: 0,0:23:43.00,0:23:45.00,Default,,0000,0000,0000,,and go to one of my neighbors.
Dialogue: 0,0:23:45.00,0:23:48.00,Default,,0000,0000,0000,,And so we can't do that infinitely without getting into trouble. We need
Dialogue: 0,0:23:48.00,0:23:53.00,Default,,0000,0000,0000,,to have a base case that stops that recursion, and the two cases that I've
Dialogue: 0,0:23:53.00,0:23:56.00,Default,,0000,0000,0000,,talked about - one is just when you have no neighbors left to go.
Dialogue: 0,0:23:56.00,0:23:57.00,Default,,0000,0000,0000,,So when you
Dialogue: 0,0:23:57.00,0:23:59.00,Default,,0000,0000,0000,,
Dialogue: 0,0:23:59.00,0:24:04.00,Default,,0000,0000,0000,,get to a node that actually, kind of, is a dead end, or that neighbor only has visited
Dialogue: 0,0:24:04.00,0:24:05.00,Default,,0000,0000,0000,,neighbors
Dialogue: 0,0:24:05.00,0:24:09.00,Default,,0000,0000,0000,,that surround it. So a
Dialogue: 0,0:24:09.00,0:24:10.00,Default,,0000,0000,0000,,very simple little piece of
Dialogue: 0,0:24:10.00,0:24:13.00,Default,,0000,0000,0000,,code that depends on recursion doing its job.
Dialogue: 0,0:24:13.00,0:24:17.00,Default,,0000,0000,0000,,In this case, we need to know which nodes we have visited, right? We're gonna have to
Dialogue: 0,0:24:17.00,0:24:19.00,Default,,0000,0000,0000,,have some kind of strategy for saying I
Dialogue: 0,0:24:19.00,0:24:21.00,Default,,0000,0000,0000,,have been here before.
Dialogue: 0,0:24:21.00,0:24:24.00,Default,,0000,0000,0000,,In this case, I'm using just a set because that's an easy thing to do.
Dialogue: 0,0:24:24.00,0:24:27.00,Default,,0000,0000,0000,,I make a set of node pointers, and I update it
Dialogue: 0,0:24:27.00,0:24:29.00,Default,,0000,0000,0000,,each time I see a new node; I add it to
Dialogue: 0,0:24:29.00,0:24:34.00,Default,,0000,0000,0000,,that set, and if I ever get to a node who is already previously visited
Dialogue: 0,0:24:34.00,0:24:38.00,Default,,0000,0000,0000,,from that, there's no reason to do any work from there; we can immediately
Dialogue: 0,0:24:38.00,0:24:41.00,Default,,0000,0000,0000,,stop. So
Dialogue: 0,0:24:41.00,0:24:43.00,Default,,0000,0000,0000,,starting that step would be empty.
Dialogue: 0,0:24:43.00,0:24:46.00,Default,,0000,0000,0000,,If the visit already contains the node that we're currently trying to visit,
Dialogue: 0,0:24:46.00,0:24:50.00,Default,,0000,0000,0000,,then there's nothing to do. Otherwise, we go ahead and add it, and there's a little node
Dialogue: 0,0:24:50.00,0:24:53.00,Default,,0000,0000,0000,,here that says we'll do something would occur. What am I trying to do here? Am I trying to print those nodes? Am
Dialogue: 0,0:24:53.00,0:24:56.00,Default,,0000,0000,0000,,I trying to draw pictures on those nodes, highlight those nodes, you know,
Dialogue: 0,0:24:56.00,0:25:00.00,Default,,0000,0000,0000,,something I'm doing with them. I don't know what it is, but this is the structure for the depth-first search
Dialogue: 0,0:25:00.00,0:25:01.00,Default,,0000,0000,0000,,here, and
Dialogue: 0,0:25:01.00,0:25:02.00,Default,,0000,0000,0000,,then
Dialogue: 0,0:25:02.00,0:25:04.00,Default,,0000,0000,0000,,for all of the neighbors,
Dialogue: 0,0:25:04.00,0:25:07.00,Default,,0000,0000,0000,,using the vector of outgoing connections,
Dialogue: 0,0:25:07.00,0:25:08.00,Default,,0000,0000,0000,,then I run a depth-first search
Dialogue: 0,0:25:08.00,0:25:11.00,Default,,0000,0000,0000,,on each of those neighbors
Dialogue: 0,0:25:11.00,0:25:14.00,Default,,0000,0000,0000,,passing that visited set by reference
Dialogue: 0,0:25:14.00,0:25:16.00,Default,,0000,0000,0000,,through the whole operation. So I will
Dialogue: 0,0:25:16.00,0:25:20.00,Default,,0000,0000,0000,,always be adding to and modifying this one set, so I will
Dialogue: 0,0:25:20.00,0:25:24.00,Default,,0000,0000,0000,,be able to know where I am and where I still need to go.
Dialogue: 0,0:25:24.00,0:25:27.00,Default,,0000,0000,0000,,So if we trace this guy in action -
Dialogue: 0,0:25:27.00,0:25:31.00,Default,,0000,0000,0000,,if I start arbitrarily from A, I say I'd like to begin with A.
Dialogue: 0,0:25:31.00,0:25:35.00,Default,,0000,0000,0000,,Then the depth-first search is gonna pick a neighbor, and let's say I happen to just work
Dialogue: 0,0:25:35.00,0:25:38.00,Default,,0000,0000,0000,,over my neighbors in alphabetical order.
Dialogue: 0,0:25:38.00,0:25:41.00,Default,,0000,0000,0000,,It would say okay, well, I've picked B. Let's go to everywhere we can get to from B. So A
Dialogue: 0,0:25:41.00,0:25:42.00,Default,,0000,0000,0000,,gets marked as visited.
Dialogue: 0,0:25:42.00,0:25:44.00,Default,,0000,0000,0000,,I move onto B; I say, well,
Dialogue: 0,0:25:44.00,0:25:48.00,Default,,0000,0000,0000,,B, search everywhere you can to from B, and B says okay, well, I need to pick a
Dialogue: 0,0:25:48.00,0:25:50.00,Default,,0000,0000,0000,,neighbor, how about I pick
Dialogue: 0,0:25:50.00,0:25:51.00,Default,,0000,0000,0000,,C? And says
Dialogue: 0,0:25:51.00,0:25:53.00,Default,,0000,0000,0000,,and now,
Dialogue: 0,0:25:53.00,0:25:56.00,Default,,0000,0000,0000,,having visited C, go everywhere you can get to from C. Well,
Dialogue: 0,0:25:56.00,0:25:59.00,Default,,0000,0000,0000,,C has no neighbors, right, no outgoing connections whatsoever.
Dialogue: 0,0:25:59.00,0:26:02.00,Default,,0000,0000,0000,,So C says, well, okay, everywhere you can get to from C is C,
Dialogue: 0,0:26:02.00,0:26:04.00,Default,,0000,0000,0000,,you know, I'm done.
Dialogue: 0,0:26:04.00,0:26:09.00,Default,,0000,0000,0000,,That will cause it to backtrack to this place, to B, and B says okay, I explored everywhere I can get to
Dialogue: 0,0:26:09.00,0:26:10.00,Default,,0000,0000,0000,,from C;
Dialogue: 0,0:26:10.00,0:26:13.00,Default,,0000,0000,0000,,what other neighbors do I have? B has no other neighbors. So, in fact, B backtracks all the way
Dialogue: 0,0:26:13.00,0:26:15.00,Default,,0000,0000,0000,,back to A.
Dialogue: 0,0:26:15.00,0:26:19.00,Default,,0000,0000,0000,,So now A says okay, well, I went everywhere I can get to from B,
Dialogue: 0,0:26:19.00,0:26:20.00,Default,,0000,0000,0000,,right? Let me look at my next neighbor.
Dialogue: 0,0:26:20.00,0:26:23.00,Default,,0000,0000,0000,,My next neighbor is C. Ah,
Dialogue: 0,0:26:23.00,0:26:25.00,Default,,0000,0000,0000,,but C, already visited,
Dialogue: 0,0:26:25.00,0:26:27.00,Default,,0000,0000,0000,,so there's no reason to
Dialogue: 0,0:26:27.00,0:26:29.00,Default,,0000,0000,0000,,go crazy on that thing. So, in fact, I can
Dialogue: 0,0:26:29.00,0:26:33.00,Default,,0000,0000,0000,,immediately see that I've visited that, so I don't have any further path to look at
Dialogue: 0,0:26:33.00,0:26:33.00,Default,,0000,0000,0000,,there.
Dialogue: 0,0:26:33.00,0:26:35.00,Default,,0000,0000,0000,,I'll hit D then
Dialogue: 0,0:26:35.00,0:26:37.00,Default,,0000,0000,0000,,as the next one in sequence. So
Dialogue: 0,0:26:37.00,0:26:40.00,Default,,0000,0000,0000,,at this point, I've done everything reachable from the B arm, everything
Dialogue: 0,0:26:40.00,0:26:43.00,Default,,0000,0000,0000,,reachable from the C arm, and now I'm starting on the D arm. I said okay, where can I get to
Dialogue: 0,0:26:43.00,0:26:44.00,Default,,0000,0000,0000,,from D?
Dialogue: 0,0:26:44.00,0:26:46.00,Default,,0000,0000,0000,,Well, I can get to E. All right,
Dialogue: 0,0:26:46.00,0:26:48.00,Default,,0000,0000,0000,,where can I get to from E?
Dialogue: 0,0:26:48.00,0:26:52.00,Default,,0000,0000,0000,,E goes to F, so the idea is you think of it going deep. It's going as far away as it
Dialogue: 0,0:26:52.00,0:26:56.00,Default,,0000,0000,0000,,can, as deep as possible, before it, kind of, unwinds
Dialogue: 0,0:26:56.00,0:26:58.00,Default,,0000,0000,0000,,getting to the F that has no neighbors
Dialogue: 0,0:26:58.00,0:27:01.00,Default,,0000,0000,0000,,and saying okay. Well, how about - where can I get to
Dialogue: 0,0:27:01.00,0:27:04.00,Default,,0000,0000,0000,,also from E? I can get to G.
Dialogue: 0,0:27:04.00,0:27:07.00,Default,,0000,0000,0000,,From G where can I get to? Nowhere,
Dialogue: 0,0:27:07.00,0:27:09.00,Default,,0000,0000,0000,,so we, kind of, unwind the
Dialogue: 0,0:27:09.00,0:27:12.00,Default,,0000,0000,0000,,D arm, and then we will eventually get back to and hit the H.
Dialogue: 0,0:27:12.00,0:27:16.00,Default,,0000,0000,0000,,So the order they actually were hit in this case happened to be alphabetical. I
Dialogue: 0,0:27:16.00,0:27:18.00,Default,,0000,0000,0000,,assigned them such that that would come out that way.
Dialogue: 0,0:27:18.00,0:27:21.00,Default,,0000,0000,0000,,That's not really a property of what depth-first search does,
Dialogue: 0,0:27:21.00,0:27:24.00,Default,,0000,0000,0000,,but think of it as like it's going as deep as possible, as far away as possible,
Dialogue: 0,0:27:24.00,0:27:28.00,Default,,0000,0000,0000,,and so it makes a choice - it's pretty much like the recursive backtrackers that we've seen. In
Dialogue: 0,0:27:28.00,0:27:31.00,Default,,0000,0000,0000,,fact, they make a choice, commit to it, and just move forward on it, never, kind of,
Dialogue: 0,0:27:31.00,0:27:35.00,Default,,0000,0000,0000,,giving a backwards glance, and only if the whole process
Dialogue: 0,0:27:35.00,0:27:35.00,Default,,0000,0000,0000,,bottoms out
Dialogue: 0,0:27:35.00,0:27:39.00,Default,,0000,0000,0000,,does it come back and start unmaking decisions and try alternatives,
Dialogue: 0,0:27:39.00,0:27:43.00,Default,,0000,0000,0000,,eventually exploring everything reachable from A
Dialogue: 0,0:27:43.00,0:27:46.00,Default,,0000,0000,0000,,when all is done and said. So if
Dialogue: 0,0:27:46.00,0:27:49.00,Default,,0000,0000,0000,,you, for example, use that on the maze,
Dialogue: 0,0:27:49.00,0:27:52.00,Default,,0000,0000,0000,,right, the depth-first search on a maze is very much the same strategy we're talking about
Dialogue: 0,0:27:52.00,0:27:53.00,Default,,0000,0000,0000,,here.
Dialogue: 0,0:27:53.00,0:27:56.00,Default,,0000,0000,0000,,Instead of the way we did it was actually breadth-first search, if you
Dialogue: 0,0:27:56.00,0:27:57.00,Default,,0000,0000,0000,,remember back to that assignment,
Dialogue: 0,0:27:57.00,0:28:00.00,Default,,0000,0000,0000,,the depth-first search alternative is actually doing it the -
Dialogue: 0,0:28:00.00,0:28:01.00,Default,,0000,0000,0000,,just go deep,
Dialogue: 0,0:28:01.00,0:28:04.00,Default,,0000,0000,0000,,make a choice, go with it, run all the way until it bottoms out,
Dialogue: 0,0:28:04.00,0:28:12.00,Default,,0000,0000,0000,,and only then back up and try some other alternatives.
Dialogue: 0,0:28:12.00,0:28:15.00,Default,,0000,0000,0000,,The breadth-first traversal, gonna hit
Dialogue: 0,0:28:15.00,0:28:16.00,Default,,0000,0000,0000,,the same nodes
Dialogue: 0,0:28:16.00,0:28:19.00,Default,,0000,0000,0000,,but just gonna hit them in a different way.
Dialogue: 0,0:28:19.00,0:28:21.00,Default,,0000,0000,0000,,If my goal were to actually hit all of them,
Dialogue: 0,0:28:21.00,0:28:25.00,Default,,0000,0000,0000,,then either of them is gonna be a fine strategy. There may be some reason why
Dialogue: 0,0:28:25.00,0:28:25.00,Default,,0000,0000,0000,,
Dialogue: 0,0:28:25.00,0:28:29.00,Default,,0000,0000,0000,,I'm hoping to stop the search early, and that actually might dictate why I would prefer
Dialogue: 0,0:28:29.00,0:28:31.00,Default,,0000,0000,0000,,which ones to look at first.
Dialogue: 0,0:28:31.00,0:28:35.00,Default,,0000,0000,0000,,The breadth-first traversal is going to explore things in terms of distance,
Dialogue: 0,0:28:35.00,0:28:40.00,Default,,0000,0000,0000,,in this case, expressed in terms of number of hops away from the starting
Dialogue: 0,0:28:40.00,0:28:40.00,Default,,0000,0000,0000,,node.
Dialogue: 0,0:28:40.00,0:28:44.00,Default,,0000,0000,0000,,So it's gonna look at everything that's one hop away, and then go back and look at
Dialogue: 0,0:28:44.00,0:28:46.00,Default,,0000,0000,0000,,everything two hops away, and then three hops away.
Dialogue: 0,0:28:46.00,0:28:49.00,Default,,0000,0000,0000,,And so if the goal, for example, was to find a node
Dialogue: 0,0:28:49.00,0:28:51.00,Default,,0000,0000,0000,,in a shortest path connection between it,
Dialogue: 0,0:28:51.00,0:28:55.00,Default,,0000,0000,0000,,then breadth-first search, by looking at all the ones one hop away, if it was a one hop
Dialogue: 0,0:28:55.00,0:28:56.00,Default,,0000,0000,0000,,path, it'll find it,
Dialogue: 0,0:28:56.00,0:28:59.00,Default,,0000,0000,0000,,and if it's a two hop path, it'll find it on that next round, and then the three hop
Dialogue: 0,0:28:59.00,0:29:00.00,Default,,0000,0000,0000,,path,
Dialogue: 0,0:29:00.00,0:29:02.00,Default,,0000,0000,0000,,and there might be paths that are 10, and 20, and 100
Dialogue: 0,0:29:02.00,0:29:03.00,Default,,0000,0000,0000,,steps long,
Dialogue: 0,0:29:03.00,0:29:06.00,Default,,0000,0000,0000,,but if I find it earlier, I won't go looking at them. It actually might prove to
Dialogue: 0,0:29:06.00,0:29:09.00,Default,,0000,0000,0000,,be a more efficient way to get to the shortest solution as opposed to depth-first
Dialogue: 0,0:29:09.00,0:29:11.00,Default,,0000,0000,0000,,search which go off and try all these deep
Dialogue: 0,0:29:11.00,0:29:14.00,Default,,0000,0000,0000,,paths that may not ever end up where I want it to be
Dialogue: 0,0:29:14.00,0:29:16.00,Default,,0000,0000,0000,,before it eventually made its way to the short
Dialogue: 0,0:29:16.00,0:29:20.00,Default,,0000,0000,0000,,solution I was wanting to find. So the thing
Dialogue: 0,0:29:20.00,0:29:21.00,Default,,0000,0000,0000,,is we have the starting node.
Dialogue: 0,0:29:21.00,0:29:24.00,Default,,0000,0000,0000,,We're gonna visit all the immediate neighbors.
Dialogue: 0,0:29:24.00,0:29:27.00,Default,,0000,0000,0000,,So, basically, a loop over the
Dialogue: 0,0:29:27.00,0:29:28.00,Default,,0000,0000,0000,,immediate one,
Dialogue: 0,0:29:28.00,0:29:31.00,Default,,0000,0000,0000,,and then while we're doing that, we're gonna actually, kind of, be gathering up that
Dialogue: 0,0:29:31.00,0:29:33.00,Default,,0000,0000,0000,,next generation.
Dialogue: 0,0:29:33.00,0:29:33.00,Default,,0000,0000,0000,,
Dialogue: 0,0:29:33.00,0:29:37.00,Default,,0000,0000,0000,,Sometimes that's called the Frontier, sort of, advancing the frontier
Dialogue: 0,0:29:37.00,0:29:39.00,Default,,0000,0000,0000,,of the nodes to explore next,
Dialogue: 0,0:29:39.00,0:29:42.00,Default,,0000,0000,0000,,so all the nodes that are two hops away,
Dialogue: 0,0:29:42.00,0:29:44.00,Default,,0000,0000,0000,,and then while we're processing the ones that are two hops away, we're gonna
Dialogue: 0,0:29:44.00,0:29:47.00,Default,,0000,0000,0000,,be gathering the frontier
Dialogue: 0,0:29:47.00,0:29:50.00,Default,,0000,0000,0000,,that is three hops away. And so at each stage we'll be, kind of, processing a
Dialogue: 0,0:29:50.00,0:29:54.00,Default,,0000,0000,0000,,generation but while assembling the generation N+1
Dialogue: 0,0:29:54.00,0:29:58.00,Default,,0000,0000,0000,,in case we need to go further to find those things.
Dialogue: 0,0:29:58.00,0:30:00.00,Default,,0000,0000,0000,,We'll use an auxiliary data structure during
Dialogue: 0,0:30:00.00,0:30:04.00,Default,,0000,0000,0000,,this. That management of the frontier, keeping track of the nodes that are, kind
Dialogue: 0,0:30:04.00,0:30:05.00,Default,,0000,0000,0000,,of,
Dialogue: 0,0:30:05.00,0:30:07.00,Default,,0000,0000,0000,,staged for the
Dialogue: 0,0:30:07.00,0:30:09.00,Default,,0000,0000,0000,,subsequent iterations,
Dialogue: 0,0:30:09.00,0:30:12.00,Default,,0000,0000,0000,,the queue is a perfect data structure for that. If I put the
Dialogue: 0,0:30:12.00,0:30:14.00,Default,,0000,0000,0000,,initial neighbors into a queue,
Dialogue: 0,0:30:14.00,0:30:19.00,Default,,0000,0000,0000,,as I dequeue them, if I put their neighbors on the back of the queue, so enqueue them
Dialogue: 0,0:30:19.00,0:30:21.00,Default,,0000,0000,0000,,behind all the one hop neighbors, then
Dialogue: 0,0:30:21.00,0:30:24.00,Default,,0000,0000,0000,,if I do that with code, as I'm processing Generation 1 off the front of the queue, I'll be
Dialogue: 0,0:30:24.00,0:30:27.00,Default,,0000,0000,0000,,stacking Generation 2 in the back of the queue,
Dialogue: 0,0:30:27.00,0:30:30.00,Default,,0000,0000,0000,,and then when all of Generation 1 is exhausted, I'll be processing Generation
Dialogue: 0,0:30:30.00,0:30:31.00,Default,,0000,0000,0000,,2,
Dialogue: 0,0:30:31.00,0:30:35.00,Default,,0000,0000,0000,,but, kind of, enqueuing Generation 3 behind it.
Dialogue: 0,0:30:35.00,0:30:39.00,Default,,0000,0000,0000,,Same deal that we had with depth-first search though is we will have to be
Dialogue: 0,0:30:39.00,0:30:41.00,Default,,0000,0000,0000,,careful about cycles will pull past that
Dialogue: 0,0:30:41.00,0:30:44.00,Default,,0000,0000,0000,,when there's more than one possibility of how we get to something, we don't
Dialogue: 0,0:30:44.00,0:30:46.00,Default,,0000,0000,0000,,want to, kind of, keep going around that cycle
Dialogue: 0,0:30:46.00,0:30:52.00,Default,,0000,0000,0000,,or do a lot of redundant work visiting nodes that we've already seen. So
Dialogue: 0,0:30:52.00,0:30:55.00,Default,,0000,0000,0000,,I have the same idea of keeping track of a set
Dialogue: 0,0:30:55.00,0:30:57.00,Default,,0000,0000,0000,,that knows what
Dialogue: 0,0:30:57.00,0:31:00.00,Default,,0000,0000,0000,,we've previously visited,
Dialogue: 0,0:31:00.00,0:31:01.00,Default,,0000,0000,0000,,and the
Dialogue: 0,0:31:01.00,0:31:05.00,Default,,0000,0000,0000,,initial node gets enqueued just, kind of, by itself, just like Generation 0 gets
Dialogue: 0,0:31:05.00,0:31:07.00,Default,,0000,0000,0000,,put into the queue,
Dialogue: 0,0:31:07.00,0:31:10.00,Default,,0000,0000,0000,,and then while the queue is not empty, so while there's still neighbors I haven't
Dialogue: 0,0:31:10.00,0:31:11.00,Default,,0000,0000,0000,,yet visited,
Dialogue: 0,0:31:11.00,0:31:13.00,Default,,0000,0000,0000,,I dequeue the frontmost one,
Dialogue: 0,0:31:13.00,0:31:16.00,Default,,0000,0000,0000,,if it hasn't already been visited on some previous iteration, then I mark it as
Dialogue: 0,0:31:16.00,0:31:17.00,Default,,0000,0000,0000,,visited,
Dialogue: 0,0:31:17.00,0:31:22.00,Default,,0000,0000,0000,,and then I enqueue all of its children or neighbors at the back of the queue.
Dialogue: 0,0:31:22.00,0:31:26.00,Default,,0000,0000,0000,,And so, as of right now, I'm processing Generation 0, that means all of Generation 1, so the
Dialogue: 0,0:31:26.00,0:31:29.00,Default,,0000,0000,0000,,neighbors that are one hop away, get placed in the queue, and then
Dialogue: 0,0:31:29.00,0:31:34.00,Default,,0000,0000,0000,,the next iteration coming out here will pull off a Generation 1,
Dialogue: 0,0:31:34.00,0:31:37.00,Default,,0000,0000,0000,,and then enqueue all of these two hop neighbors.
Dialogue: 0,0:31:37.00,0:31:40.00,Default,,0000,0000,0000,,Come back and other Generation 1's will get pulled off, enqueue all their two hop
Dialogue: 0,0:31:40.00,0:31:44.00,Default,,0000,0000,0000,,neighbors, and so the two hop generation will, kind of, be built up behind, and then
Dialogue: 0,0:31:44.00,0:31:48.00,Default,,0000,0000,0000,,once the last of the one hop generation gets managed,
Dialogue: 0,0:31:48.00,0:31:51.00,Default,,0000,0000,0000,,start processing the Generation 2 and so on.
Dialogue: 0,0:31:51.00,0:31:55.00,Default,,0000,0000,0000,,And so this will keep going while the queue has some
Dialogue: 0,0:31:55.00,0:31:58.00,Default,,0000,0000,0000,,contents in there. So that means some neighbors
Dialogue: 0,0:31:58.00,0:32:01.00,Default,,0000,0000,0000,,we have connections to that we haven't yet had a chance to explore, and
Dialogue: 0,0:32:01.00,0:32:05.00,Default,,0000,0000,0000,,either we will find out that they have all been visited, so this will end when
Dialogue: 0,0:32:05.00,0:32:09.00,Default,,0000,0000,0000,,all of the nodes that are in the queue have been visited or
Dialogue: 0,0:32:09.00,0:32:14.00,Default,,0000,0000,0000,,there are no more neighbors to enqueue. So we've gotten to those dead ends or those cycles
Dialogue: 0,0:32:14.00,0:32:25.00,Default,,0000,0000,0000,,that mean we've reach everything that was reachable from that start node.
Dialogue: 0,0:32:25.00,0:32:28.00,Default,,0000,0000,0000,,And so I've traced this guy
Dialogue: 0,0:32:28.00,0:32:30.00,Default,,0000,0000,0000,,to see it doing its work.
Dialogue: 0,0:32:30.00,0:32:33.00,Default,,0000,0000,0000,,So if I start again with A,
Dialogue: 0,0:32:33.00,0:32:36.00,Default,,0000,0000,0000,,and, again, assuming that I'm gonna process my nodes
Dialogue: 0,0:32:36.00,0:32:40.00,Default,,0000,0000,0000,,in alphabetical order when I have children, so I will through and I
Dialogue: 0,0:32:40.00,0:32:44.00,Default,,0000,0000,0000,,will enqueue, so the queue right now has just node A in it. I pull it off. I say
Dialogue: 0,0:32:44.00,0:32:45.00,Default,,0000,0000,0000,,have I visited? No, I have not.
Dialogue: 0,0:32:45.00,0:32:47.00,Default,,0000,0000,0000,,So then I mark it as visited,
Dialogue: 0,0:32:47.00,0:32:52.00,Default,,0000,0000,0000,,and now for each of its neighboring nodes, B, C, D, H, I'm gonna put those into
Dialogue: 0,0:32:52.00,0:32:54.00,Default,,0000,0000,0000,,the queue,
Dialogue: 0,0:32:54.00,0:32:57.00,Default,,0000,0000,0000,,and so then they're loaded up, and then I come back around, I say do I still have stuff in the queue? I
Dialogue: 0,0:32:57.00,0:33:01.00,Default,,0000,0000,0000,,do, so let's take out the first thing that was put in; it was B. Okay,
Dialogue: 0,0:33:01.00,0:33:05.00,Default,,0000,0000,0000,,and I'll say okay, well, where can you get to from B? You can get to C, so I'm gonna put C in the queue. Now,
Dialogue: 0,0:33:05.00,0:33:09.00,Default,,0000,0000,0000,,C is actually already in the queue, but we're gonna pull it out
Dialogue: 0,0:33:09.00,0:33:12.00,Default,,0000,0000,0000,,earlier in terms it'll get handled by the
Dialogue: 0,0:33:12.00,0:33:14.00,Default,,0000,0000,0000,,visiting status later.
Dialogue: 0,0:33:14.00,0:33:16.00,Default,,0000,0000,0000,,So, okay, we'll put C, D, and E in
Dialogue: 0,0:33:16.00,0:33:20.00,Default,,0000,0000,0000,,and then put C behind it. So right now, we'll have C, D, H, and C again.
Dialogue: 0,0:33:20.00,0:33:24.00,Default,,0000,0000,0000,,It'll find the C that's in the front there. It'll say where can you get to from C?
Dialogue: 0,0:33:24.00,0:33:24.00,Default,,0000,0000,0000,,Nowhere,
Dialogue: 0,0:33:24.00,0:33:26.00,Default,,0000,0000,0000,,so no additional
Dialogue: 0,0:33:26.00,0:33:28.00,Default,,0000,0000,0000,,Generation 2's are added by that one.
Dialogue: 0,0:33:28.00,0:33:31.00,Default,,0000,0000,0000,,I'll look at D, and I'll say okay, well, what Generation 2's do we have from D? It says, well, I can
Dialogue: 0,0:33:31.00,0:33:32.00,Default,,0000,0000,0000,,get to E. All right, so put E on the
Dialogue: 0,0:33:32.00,0:33:34.00,Default,,0000,0000,0000,,back of the
Dialogue: 0,0:33:34.00,0:33:36.00,Default,,0000,0000,0000,,
Dialogue: 0,0:33:36.00,0:33:39.00,Default,,0000,0000,0000,,queue. Look at H; where can H get to? H can get to G,
Dialogue: 0,0:33:39.00,0:33:42.00,Default,,0000,0000,0000,,so go ahead and put G on the back of the queue.
Dialogue: 0,0:33:42.00,0:33:45.00,Default,,0000,0000,0000,,So now, it comes back around to the things that are two hops away.
Dialogue: 0,0:33:45.00,0:33:47.00,Default,,0000,0000,0000,,The first one it's gonna pull off is C. It's
Dialogue: 0,0:33:47.00,0:33:49.00,Default,,0000,0000,0000,,gonna say, well, C is already visited,
Dialogue: 0,0:33:49.00,0:33:53.00,Default,,0000,0000,0000,,so there's no need to redundantly visit that or do anything with that.
Dialogue: 0,0:33:53.00,0:33:54.00,Default,,0000,0000,0000,,It passes over C. It
Dialogue: 0,0:33:54.00,0:33:56.00,Default,,0000,0000,0000,,finds the E
Dialogue: 0,0:33:56.00,0:33:58.00,Default,,0000,0000,0000,,that's behind that,
Dialogue: 0,0:33:58.00,0:34:00.00,Default,,0000,0000,0000,,and then it finds the G that was behind the
Dialogue: 0,0:34:00.00,0:34:03.00,Default,,0000,0000,0000,,H. The E also enqueued the F
Dialogue: 0,0:34:03.00,0:34:07.00,Default,,0000,0000,0000,,that was four hops, and the very last one, right, output will be that F that was
Dialogue: 0,0:34:07.00,0:34:09.00,Default,,0000,0000,0000,,only reachable by taking
Dialogue: 0,0:34:09.00,0:34:12.00,Default,,0000,0000,0000,,three hops away from the thing. So this one's, kind of,
Dialogue: 0,0:34:12.00,0:34:13.00,Default,,0000,0000,0000,,working radially. The
Dialogue: 0,0:34:13.00,0:34:16.00,Default,,0000,0000,0000,,idea that I'm looking at all the things that I can get to, kind of, in one hop
Dialogue: 0,0:34:16.00,0:34:19.00,Default,,0000,0000,0000,,are my first generation, then two hops, then three hops,
Dialogue: 0,0:34:19.00,0:34:23.00,Default,,0000,0000,0000,,and so it's like throwing a stone in the water and watching it ripple out
Dialogue: 0,0:34:23.00,0:34:26.00,Default,,0000,0000,0000,,that the visiting
Dialogue: 0,0:34:26.00,0:34:29.00,Default,,0000,0000,0000,,is managed in terms of, kind of, growing length of path,
Dialogue: 0,0:34:29.00,0:34:32.00,Default,,0000,0000,0000,,and number of hops that it took to get there.
Dialogue: 0,0:34:32.00,0:34:37.00,Default,,0000,0000,0000,,So this is the strategy that you used for maze solving, if you remember.
Dialogue: 0,0:34:37.00,0:34:37.00,Default,,0000,0000,0000,,That
Dialogue: 0,0:34:37.00,0:34:42.00,Default,,0000,0000,0000,,what you were tracking was the queue of paths where the path was
Dialogue: 0,0:34:42.00,0:34:44.00,Default,,0000,0000,0000,,AB, or ADC, or
Dialogue: 0,0:34:44.00,0:34:46.00,Default,,0000,0000,0000,,ADE, and that they grew
Dialogue: 0,0:34:46.00,0:34:47.00,Default,,0000,0000,0000,,
Dialogue: 0,0:34:47.00,0:34:50.00,Default,,0000,0000,0000,,step wise. That, kind of, each iteration through the
Dialogue: 0,0:34:50.00,0:34:54.00,Default,,0000,0000,0000,,traversal there where you're saying, okay, well, I've seen all the paths that are one hop. Now I've seen all the ones of two,
Dialogue: 0,0:34:54.00,0:34:56.00,Default,,0000,0000,0000,,now the ones three, and four, and five,
Dialogue: 0,0:34:56.00,0:34:58.00,Default,,0000,0000,0000,,and when you keep doing that, eventually you get to the hop,
Dialogue: 0,0:34:58.00,0:35:01.00,Default,,0000,0000,0000,,you know, 75, which leads you
Dialogue: 0,0:35:01.00,0:35:05.00,Default,,0000,0000,0000,,all the way to the goal, and since you have looked at all the paths that were
Dialogue: 0,0:35:05.00,0:35:09.00,Default,,0000,0000,0000,,74 and shorter, the first path that you dequeue that leads to your goal
Dialogue: 0,0:35:09.00,0:35:12.00,Default,,0000,0000,0000,,must be the best or the shortest overall
Dialogue: 0,0:35:12.00,0:35:13.00,Default,,0000,0000,0000,,because
Dialogue: 0,0:35:13.00,0:35:15.00,Default,,0000,0000,0000,,of the order you processed them.
Dialogue: 0,0:35:15.00,0:35:18.00,Default,,0000,0000,0000,,That's not true in depth-first search, right? That depth-first search might find a much
Dialogue: 0,0:35:18.00,0:35:21.00,Default,,0000,0000,0000,,longer and more circuitous path that led to the goal
Dialogue: 0,0:35:21.00,0:35:25.00,Default,,0000,0000,0000,,when there is a shorter one that would be eventually found if I had a graph that
Dialogue: 0,0:35:25.00,0:35:28.00,Default,,0000,0000,0000,,looked,
Dialogue: 0,0:35:28.00,0:35:36.00,Default,,0000,0000,0000,,you know, had this long path, let's say,
Dialogue: 0,0:35:36.00,0:35:41.00,Default,,0000,0000,0000,,and so this is goal node, let's say, and this is the start node that
Dialogue: 0,0:35:41.00,0:35:44.00,Default,,0000,0000,0000,,there could be a two hop path, kind of, off to this angle,
Dialogue: 0,0:35:44.00,0:35:47.00,Default,,0000,0000,0000,,but if this was the first one explored in the depth-first, right,
Dialogue: 0,0:35:47.00,0:35:50.00,Default,,0000,0000,0000,,it could eventually, kind of, work its way all the way around through this
Dialogue: 0,0:35:50.00,0:35:52.00,Default,,0000,0000,0000,,eight hop path, and say, okay, well, I found it, right?
Dialogue: 0,0:35:52.00,0:35:55.00,Default,,0000,0000,0000,,It would be the first one we found, but there's no guarantee that would be the
Dialogue: 0,0:35:55.00,0:35:58.00,Default,,0000,0000,0000,,shortest in depth-first search, right? It would just happen to be the one that based on
Dialogue: 0,0:35:58.00,0:36:01.00,Default,,0000,0000,0000,,its arbitrary choice of which
Dialogue: 0,0:36:01.00,0:36:04.00,Default,,0000,0000,0000,,neighbors to pursue it happened to get to that there could be a shorter
Dialogue: 0,0:36:04.00,0:36:08.00,Default,,0000,0000,0000,,one that would be found later in the traversal. That's not true in
Dialogue: 0,0:36:08.00,0:36:12.00,Default,,0000,0000,0000,,the breadth-first search strategy because it will be looking at this, and then these two,
Dialogue: 0,0:36:12.00,0:36:16.00,Default,,0000,0000,0000,,and then these two, and, kind of, working its way outward down those edges.
Dialogue: 0,0:36:16.00,0:36:19.00,Default,,0000,0000,0000,,So as soon as we get to one that hits the goal, we
Dialogue: 0,0:36:19.00,0:36:25.00,Default,,0000,0000,0000,,know we have found the shortest we can have. Question?
Dialogue: 0,0:36:25.00,0:36:28.00,Default,,0000,0000,0000,,In that case,
Dialogue: 0,0:36:28.00,0:36:33.00,Default,,0000,0000,0000,,you could return, okay, we need two
Dialogue: 0,0:36:33.00,0:36:34.00,Default,,0000,0000,0000,,jumps to get to
Dialogue: 0,0:36:34.00,0:36:35.00,Default,,0000,0000,0000,,the goal,
Dialogue: 0,0:36:35.00,0:36:36.00,Default,,0000,0000,0000,,like, as far
Dialogue: 0,0:36:36.00,0:36:40.00,Default,,0000,0000,0000,,winning the goal. Yeah. How do we remember which path led us there?
Dialogue: 0,0:36:40.00,0:36:42.00,Default,,0000,0000,0000,,So if you were really doing that, you know, in terms of depth-first search, what
Dialogue: 0,0:36:42.00,0:36:46.00,Default,,0000,0000,0000,,you'd probably be tracking is what's the path? Probably a stack that said here's the stack
Dialogue: 0,0:36:46.00,0:36:49.00,Default,,0000,0000,0000,,that led to that path. Let me hold
Dialogue: 0,0:36:49.00,0:36:53.00,Default,,0000,0000,0000,,onto this, right, and I will compare it to these alternatives. So I'll try it on Neighbor 1,
Dialogue: 0,0:36:53.00,0:36:54.00,Default,,0000,0000,0000,,get the stack back from that; it's the best.
Dialogue: 0,0:36:54.00,0:36:58.00,Default,,0000,0000,0000,,Try it on Neighbor 2, get that stack back, see which one is smaller and use
Dialogue: 0,0:36:58.00,0:37:01.00,Default,,0000,0000,0000,,that as the better choice, and so, eventually, when I tried it out this side, I'd get
Dialogue: 0,0:37:01.00,0:37:03.00,Default,,0000,0000,0000,,the stack back that was just two,
Dialogue: 0,0:37:03.00,0:37:06.00,Default,,0000,0000,0000,,and I could say, yeah, that was better than this ten step path I had over here, so I
Dialogue: 0,0:37:06.00,0:37:09.00,Default,,0000,0000,0000,,will prefer that. So just using your standard, kind of, backtracking with
Dialogue: 0,0:37:09.00,0:37:13.00,Default,,0000,0000,0000,,using your return values, incorporating them, and deciding which was better.
Dialogue: 0,0:37:13.00,0:37:14.00,Default,,0000,0000,0000,,And so in this case,
Dialogue: 0,0:37:14.00,0:37:16.00,Default,,0000,0000,0000,,the depth-first search
Dialogue: 0,0:37:16.00,0:37:19.00,Default,,0000,0000,0000,,can't really be pruned very easily
Dialogue: 0,0:37:19.00,0:37:24.00,Default,,0000,0000,0000,,because it has to, kind of, explore the whole thing to know that this
Dialogue: 0,0:37:24.00,0:37:26.00,Default,,0000,0000,0000,,short little path right over here happened to be just
Dialogue: 0,0:37:26.00,0:37:29.00,Default,,0000,0000,0000,,arbitrarily examined last, whereas, the breadth-first search actually does, kind of, because
Dialogue: 0,0:37:29.00,0:37:31.00,Default,,0000,0000,0000,,it's prioritizing by
Dialogue: 0,0:37:31.00,0:37:35.00,Default,,0000,0000,0000,,order of length. If the goal was shortest path, it will find it sooner and be able to
Dialogue: 0,0:37:35.00,0:37:35.00,Default,,0000,0000,0000,,stop
Dialogue: 0,0:37:35.00,0:37:39.00,Default,,0000,0000,0000,,when it found it rather than look at these longer paths. So it won't end up -
Dialogue: 0,0:37:39.00,0:37:42.00,Default,,0000,0000,0000,,if there were hundreds of other paths over here, breadth-first search won't actually
Dialogue: 0,0:37:42.00,0:37:47.00,Default,,0000,0000,0000,,have to ever reach them or explore them.
Dialogue: 0,0:37:47.00,0:37:52.00,Default,,0000,0000,0000,,So there are a lot of things that actually end up being graph search in disguise. That's why
Dialogue: 0,0:37:52.00,0:37:54.00,Default,,0000,0000,0000,,a, kind of, a graph is a great data structure to, kind of, get to in
Dialogue: 0,0:37:54.00,0:37:57.00,Default,,0000,0000,0000,,106b because there are lots of problems
Dialogue: 0,0:37:57.00,0:38:01.00,Default,,0000,0000,0000,,that, in the end, if you can model them using the same
Dialogue: 0,0:38:01.00,0:38:03.00,Default,,0000,0000,0000,,setup of nodes, and arcs, and traversals,
Dialogue: 0,0:38:03.00,0:38:06.00,Default,,0000,0000,0000,,that you can answer interesting questions about that data by applying
Dialogue: 0,0:38:06.00,0:38:09.00,Default,,0000,0000,0000,,the same graph search techniques.
Dialogue: 0,0:38:09.00,0:38:12.00,Default,,0000,0000,0000,,So as long as you want to know things like, well, which nodes are reachable from this node at
Dialogue: 0,0:38:12.00,0:38:12.00,Default,,0000,0000,0000,,all?
Dialogue: 0,0:38:12.00,0:38:14.00,Default,,0000,0000,0000,,And then
Dialogue: 0,0:38:14.00,0:38:17.00,Default,,0000,0000,0000,,that just means, okay, I'm here and I want to get to these places; what places could
Dialogue: 0,0:38:17.00,0:38:18.00,Default,,0000,0000,0000,,I get to? Or
Dialogue: 0,0:38:18.00,0:38:21.00,Default,,0000,0000,0000,,knowing what courses I could take
Dialogue: 0,0:38:21.00,0:38:25.00,Default,,0000,0000,0000,,that would lead me to a CS degree, it's, kind of, like well, looking for the ones
Dialogue: 0,0:38:25.00,0:38:29.00,Default,,0000,0000,0000,,that lead to having all your graduation requirements
Dialogue: 0,0:38:29.00,0:38:32.00,Default,,0000,0000,0000,,satisfied, and each of those arcs could be a course you could take, right, how close did
Dialogue: 0,0:38:32.00,0:38:35.00,Default,,0000,0000,0000,,that get you to the goal? How can I get to the
Dialogue: 0,0:38:35.00,0:38:40.00,Default,,0000,0000,0000,,place I'd like to be, or what are the places that this course satisfies
Dialogue: 0,0:38:40.00,0:38:41.00,Default,,0000,0000,0000,,requirements that lead to?
Dialogue: 0,0:38:41.00,0:38:44.00,Default,,0000,0000,0000,,Knowing things about
Dialogue: 0,0:38:44.00,0:38:47.00,Default,,0000,0000,0000,,connectivity is, kind of, useful in things like the, kind of, bacon numbers or
Dialogue: 0,0:38:47.00,0:38:50.00,Default,,0000,0000,0000,,erdish numbers where people want to know, well, how close am I to greatness by -
Dialogue: 0,0:38:50.00,0:38:54.00,Default,,0000,0000,0000,,have I been in a movie with somebody who was in a movie, who was in a movie with Kevin Bacon? And,
Dialogue: 0,0:38:54.00,0:38:55.00,Default,,0000,0000,0000,,for me, it turns out
Dialogue: 0,0:38:55.00,0:38:57.00,Default,,0000,0000,0000,,zero; I have been in no movies. But have
Dialogue: 0,0:38:57.00,0:38:59.00,Default,,0000,0000,0000,,you written a paper with someone who then
Dialogue: 0,0:38:59.00,0:39:02.00,Default,,0000,0000,0000,,connects through a chain to some other famous person, right? Tells you about
Dialogue: 0,0:39:02.00,0:39:06.00,Default,,0000,0000,0000,,your, kind of, social network distance or something, or I'm linked in. You're trying to get a
Dialogue: 0,0:39:06.00,0:39:09.00,Default,,0000,0000,0000,,new job, and you want to find somebody to introduce you to
Dialogue: 0,0:39:09.00,0:39:13.00,Default,,0000,0000,0000,,the head of this cool company. It's, like, figuring who you know who knows them, right?
Dialogue: 0,0:39:13.00,0:39:18.00,Default,,0000,0000,0000,,It's finding paths through a social network graph.
Dialogue: 0,0:39:18.00,0:39:19.00,Default,,0000,0000,0000,,Finding out things like
Dialogue: 0,0:39:19.00,0:39:22.00,Default,,0000,0000,0000,,are there paths with cycles? What's the shortest path
Dialogue: 0,0:39:22.00,0:39:25.00,Default,,0000,0000,0000,,through the cycle, longest path through the cycle often tells you about things about
Dialogue: 0,0:39:25.00,0:39:27.00,Default,,0000,0000,0000,,redundancies in that structure
Dialogue: 0,0:39:27.00,0:39:31.00,Default,,0000,0000,0000,,that, for example, when you're building a network infrastructure, sometimes you do have
Dialogue: 0,0:39:31.00,0:39:34.00,Default,,0000,0000,0000,,cycles in it because you actually want to have multiple ways to get to things in case
Dialogue: 0,0:39:34.00,0:39:37.00,Default,,0000,0000,0000,,there's a breakdown. Like if there's a freeway accident, you want to have another way
Dialogue: 0,0:39:37.00,0:39:38.00,Default,,0000,0000,0000,,to get around it,
Dialogue: 0,0:39:38.00,0:39:41.00,Default,,0000,0000,0000,,but you are interested in, maybe, trying to keep your cost down is trying to find
Dialogue: 0,0:39:41.00,0:39:47.00,Default,,0000,0000,0000,,out where are the right places to put in those redundancies, those cycles that
Dialogue: 0,0:39:47.00,0:39:50.00,Default,,0000,0000,0000,,give you the best benefit with the least cost.
Dialogue: 0,0:39:50.00,0:39:54.00,Default,,0000,0000,0000,,Trying to find things like a continuous path that visits all the nodes once and exactly
Dialogue: 0,0:39:54.00,0:39:57.00,Default,,0000,0000,0000,,once, especially doing so efficiently, picking a short
Dialogue: 0,0:39:57.00,0:40:00.00,Default,,0000,0000,0000,,overall path for that. We talked a little bit about that in terms of what's called the
Dialogue: 0,0:40:00.00,0:40:02.00,Default,,0000,0000,0000,,traveling salesman problem.
Dialogue: 0,0:40:02.00,0:40:04.00,Default,,0000,0000,0000,,You are trying to get from - you have ten
Dialogue: 0,0:40:04.00,0:40:06.00,Default,,0000,0000,0000,,cities to visit on your book tour. You don't want to spend all your lifetime
Dialogue: 0,0:40:06.00,0:40:08.00,Default,,0000,0000,0000,,on a plane. What's the
Dialogue: 0,0:40:08.00,0:40:13.00,Default,,0000,0000,0000,,path of crisscrossing the country that gets you to all ten of those with the least
Dialogue: 0,0:40:13.00,0:40:15.00,Default,,0000,0000,0000,,time painfully
Dialogue: 0,0:40:15.00,0:40:17.00,Default,,0000,0000,0000,,spent on an airline? And so
Dialogue: 0,0:40:17.00,0:40:20.00,Default,,0000,0000,0000,,those are just graph search problems. You have these nodes. You have these arcs.
Dialogue: 0,0:40:20.00,0:40:21.00,Default,,0000,0000,0000,,How can you
Dialogue: 0,0:40:21.00,0:40:23.00,Default,,0000,0000,0000,,traverse them and visit
Dialogue: 0,0:40:23.00,0:40:25.00,Default,,0000,0000,0000,,and come up with
Dialogue: 0,0:40:25.00,0:40:27.00,Default,,0000,0000,0000,,a good solution. There's other
Dialogue: 0,0:40:27.00,0:40:30.00,Default,,0000,0000,0000,,problems I think that are kind of neat. Word letters, we used to give out an assignment on word letters. We
Dialogue: 0,0:40:30.00,0:40:31.00,Default,,0000,0000,0000,,didn't this time, but I thought it was an
Dialogue: 0,0:40:31.00,0:40:34.00,Default,,0000,0000,0000,,interesting problem to think about. The idea of
Dialogue: 0,0:40:34.00,0:40:36.00,Default,,0000,0000,0000,,how it is you can transform
Dialogue: 0,0:40:36.00,0:40:41.00,Default,,0000,0000,0000,,one letter at a time from one word to another is very much a
Dialogue: 0,0:40:41.00,0:40:45.00,Default,,0000,0000,0000,,graph problem behind the scenes, and that largely a breadth-first
Dialogue: 0,0:40:45.00,0:40:47.00,Default,,0000,0000,0000,,traversal is exactly what you're looking for there. How
Dialogue: 0,0:40:47.00,0:40:51.00,Default,,0000,0000,0000,,can I transform this with the shortest number of steps is, kind of,
Dialogue: 0,0:40:51.00,0:40:54.00,Default,,0000,0000,0000,,working radially out from the starting word.
Dialogue: 0,0:40:54.00,0:40:54.00,Default,,0000,0000,0000,,
Dialogue: 0,0:40:54.00,0:40:58.00,Default,,0000,0000,0000,,Your boggle board turns out, really, is just a graph. If
Dialogue: 0,0:40:58.00,0:41:01.00,Default,,0000,0000,0000,,you think of
Dialogue: 0,0:41:01.00,0:41:07.00,Default,,0000,0000,0000,,having this sequence of letters
Dialogue: 0,0:41:07.00,0:41:12.00,Default,,0000,0000,0000,,that you're trying to work through,
Dialogue: 0,0:41:12.00,0:41:16.00,Default,,0000,0000,0000,,that really each of these letters can actually just be thought of as a node,
Dialogue: 0,0:41:16.00,0:41:20.00,Default,,0000,0000,0000,,and then the connections it has are to its eight neighbors, and that finding
Dialogue: 0,0:41:20.00,0:41:24.00,Default,,0000,0000,0000,,words in there, especially finding paths, starting from
Dialogue: 0,0:41:24.00,0:41:27.00,Default,,0000,0000,0000,,this node that lead away, that don't revisit, so, in fact, doing breadth-first
Dialogue: 0,0:41:27.00,0:41:31.00,Default,,0000,0000,0000,,or depth-first search. You most likely did depth-first search when you were writing the
Dialogue: 0,0:41:31.00,0:41:32.00,Default,,0000,0000,0000,,implementation of boggle,
Dialogue: 0,0:41:32.00,0:41:35.00,Default,,0000,0000,0000,,but that's, kind of, a deep search on I found an A. I found a P. I found a P, and, kind
Dialogue: 0,0:41:35.00,0:41:40.00,Default,,0000,0000,0000,,of, keeps going as long as that path looks viable. So, in this case, that the arc
Dialogue: 0,0:41:40.00,0:41:41.00,Default,,0000,0000,0000,,information we're using is
Dialogue: 0,0:41:41.00,0:41:44.00,Default,,0000,0000,0000,,having a sub of those letters, do they form a prefix that could be leading
Dialogue: 0,0:41:44.00,0:41:45.00,Default,,0000,0000,0000,,somewhere good,
Dialogue: 0,0:41:45.00,0:41:47.00,Default,,0000,0000,0000,,and then the, kind of, recursion bottoming out when
Dialogue: 0,0:41:47.00,0:41:52.00,Default,,0000,0000,0000,,we have run ourselves into a corner where we have no unvisited nodes
Dialogue: 0,0:41:52.00,0:41:53.00,Default,,0000,0000,0000,,that neighbor us,
Dialogue: 0,0:41:53.00,0:41:57.00,Default,,0000,0000,0000,,or only nodes that would extend to a prefix that no longer forms any
Dialogue: 0,0:41:57.00,0:41:58.00,Default,,0000,0000,0000,,viable words
Dialogue: 0,0:41:58.00,0:42:01.00,Default,,0000,0000,0000,,as a search problem.
Dialogue: 0,0:42:01.00,0:42:04.00,Default,,0000,0000,0000,,So it feels like everything you've done this quarter has actually been a graph in disguise; I just didn't
Dialogue: 0,0:42:04.00,0:42:08.00,Default,,0000,0000,0000,,tell you. The maze problem is very much a graph search problem, building a
Dialogue: 0,0:42:08.00,0:42:10.00,Default,,0000,0000,0000,,graph and searching it.
Dialogue: 0,0:42:10.00,0:42:13.00,Default,,0000,0000,0000,,Another one that I think is, kind of, neat to think about is, kind of, related to the idea of word letters
Dialogue: 0,0:42:13.00,0:42:18.00,Default,,0000,0000,0000,,is that often when you mistype a word, a word
Dialogue: 0,0:42:18.00,0:42:19.00,Default,,0000,0000,0000,,processor will suggest to you
Dialogue: 0,0:42:19.00,0:42:22.00,Default,,0000,0000,0000,,here's a word that you might have meant instead. You type a word that it doesn't
Dialogue: 0,0:42:22.00,0:42:24.00,Default,,0000,0000,0000,,have in its lexicon, and it says, well,
Dialogue: 0,0:42:24.00,0:42:25.00,Default,,0000,0000,0000,,that could just be
Dialogue: 0,0:42:25.00,0:42:28.00,Default,,0000,0000,0000,,a word I don't know, but it also could mean that you actually mistyped something, and so
Dialogue: 0,0:42:28.00,0:42:31.00,Default,,0000,0000,0000,,what you want to look at is having neighboring nodes,
Dialogue: 0,0:42:31.00,0:42:33.00,Default,,0000,0000,0000,,sort of, diagramming a graph
Dialogue: 0,0:42:33.00,0:42:35.00,Default,,0000,0000,0000,,of all the words you know of
Dialogue: 0,0:42:35.00,0:42:39.00,Default,,0000,0000,0000,,and then the, kind of, permutations, the tiny little twiddles to that word that
Dialogue: 0,0:42:39.00,0:42:41.00,Default,,0000,0000,0000,,are neighbors to it so that
Dialogue: 0,0:42:41.00,0:42:44.00,Default,,0000,0000,0000,,you could describe a set of suggestions
Dialogue: 0,0:42:44.00,0:42:47.00,Default,,0000,0000,0000,,as being those things that are within a certain
Dialogue: 0,0:42:47.00,0:42:50.00,Default,,0000,0000,0000,,hop distance from the original mistyped word. And
Dialogue: 0,0:42:50.00,0:42:53.00,Default,,0000,0000,0000,,so you could say, yeah, things that have two letters different are probably
Dialogue: 0,0:42:53.00,0:42:56.00,Default,,0000,0000,0000,,close enough, but things that have three or more letters different aren't actually
Dialogue: 0,0:42:56.00,0:42:58.00,Default,,0000,0000,0000,,likely to be
Dialogue: 0,0:42:58.00,0:43:00.00,Default,,0000,0000,0000,,the mistyped word,
Dialogue: 0,0:43:00.00,0:43:04.00,Default,,0000,0000,0000,,and then that, kind of, leads to supporting things like wildcard searches
Dialogue: 0,0:43:04.00,0:43:08.00,Default,,0000,0000,0000,,where you're trying to remember whether it's E-R-A-T or A-R-T-E at the
Dialogue: 0,0:43:08.00,0:43:10.00,Default,,0000,0000,0000,,end of desperate.
Dialogue: 0,0:43:10.00,0:43:14.00,Default,,0000,0000,0000,,Those things could be modeled as, kind of, like they search through a graph space where
Dialogue: 0,0:43:14.00,0:43:16.00,Default,,0000,0000,0000,,you're modeling those letters, and then there's, like, a
Dialogue: 0,0:43:16.00,0:43:20.00,Default,,0000,0000,0000,,branching where you try all of the letters coming out of D-E-S-P, seeing if any
Dialogue: 0,0:43:20.00,0:43:23.00,Default,,0000,0000,0000,,of them lead to an R-A-T-E.
Dialogue: 0,0:43:23.00,0:43:26.00,Default,,0000,0000,0000,,So the last thing I wanted
Dialogue: 0,0:43:26.00,0:43:28.00,Default,,0000,0000,0000,,to just bring up, and this is the one that's going into this week's assignment. I'm just
Dialogue: 0,0:43:28.00,0:43:31.00,Default,,0000,0000,0000,,gonna actually show it to you to, kind of, get you thinking about it because it's
Dialogue: 0,0:43:31.00,0:43:35.00,Default,,0000,0000,0000,,actually the problem at hand that you're gonna be solving
Dialogue: 0,0:43:35.00,0:43:36.00,Default,,0000,0000,0000,,is that
Dialogue: 0,0:43:36.00,0:43:41.00,Default,,0000,0000,0000,,the one of where I'm interested in finding the shortest path, but I'm gonna add in
Dialogue: 0,0:43:41.00,0:43:43.00,Default,,0000,0000,0000,,this new idea that
Dialogue: 0,0:43:43.00,0:43:45.00,Default,,0000,0000,0000,,all hops are not created equal.
Dialogue: 0,0:43:45.00,0:43:49.00,Default,,0000,0000,0000,,That a flight from San Francisco to Seattle is a shorter distance than the
Dialogue: 0,0:43:49.00,0:43:52.00,Default,,0000,0000,0000,,one that goes from San Francisco to Boston,
Dialogue: 0,0:43:52.00,0:43:53.00,Default,,0000,0000,0000,,and if I'm interested in getting
Dialogue: 0,0:43:53.00,0:43:57.00,Default,,0000,0000,0000,,to someplace, it's not just that I would like to take a direct flight. I'd also
Dialogue: 0,0:43:57.00,0:44:00.00,Default,,0000,0000,0000,,like to take the set of flights that involves the least, kind of, going out of my way,
Dialogue: 0,0:44:00.00,0:44:03.00,Default,,0000,0000,0000,,and going through other cities, and other directions.
Dialogue: 0,0:44:03.00,0:44:07.00,Default,,0000,0000,0000,,And so in this case, a breadth-first search is a little bit too simplistic.
Dialogue: 0,0:44:07.00,0:44:10.00,Default,,0000,0000,0000,,That if I just look at all the places I can get to in one hop,
Dialogue: 0,0:44:10.00,0:44:11.00,Default,,0000,0000,0000,,
Dialogue: 0,0:44:11.00,0:44:15.00,Default,,0000,0000,0000,,those are not really equally
Dialogue: 0,0:44:15.00,0:44:16.00,Default,,0000,0000,0000,,weighted
Dialogue: 0,0:44:16.00,0:44:19.00,Default,,0000,0000,0000,,in terms of my goal of minimizing my total path distance,
Dialogue: 0,0:44:19.00,0:44:22.00,Default,,0000,0000,0000,,but if I, instead, prioritize -
Dialogue: 0,0:44:22.00,0:44:25.00,Default,,0000,0000,0000,,prioritize in your mind, immediately conjure up images of the
Dialogue: 0,0:44:25.00,0:44:26.00,Default,,0000,0000,0000,,priority queue,
Dialogue: 0,0:44:26.00,0:44:28.00,Default,,0000,0000,0000,,to look at paths that are,
Dialogue: 0,0:44:28.00,0:44:32.00,Default,,0000,0000,0000,,if I'm trying to minimize total distance, the shortest path, even if they
Dialogue: 0,0:44:32.00,0:44:36.00,Default,,0000,0000,0000,,represent several hops, if they're still shorter - if I have three flights, and each are
Dialogue: 0,0:44:36.00,0:44:37.00,Default,,0000,0000,0000,,100 miles,
Dialogue: 0,0:44:37.00,0:44:40.00,Default,,0000,0000,0000,,then they represent a flight of 300 total miles,
Dialogue: 0,0:44:40.00,0:44:44.00,Default,,0000,0000,0000,,and that's still preferred to one that actually is 2,000 miles or 7,000 miles
Dialogue: 0,0:44:44.00,0:44:45.00,Default,,0000,0000,0000,,going to Asia
Dialogue: 0,0:44:45.00,0:44:49.00,Default,,0000,0000,0000,,alternatively. And so if I worked on a breadth-first that's been modified by a total
Dialogue: 0,0:44:49.00,0:44:50.00,Default,,0000,0000,0000,,distance,
Dialogue: 0,0:44:50.00,0:44:51.00,Default,,0000,0000,0000,,that it would be a way
Dialogue: 0,0:44:51.00,0:44:54.00,Default,,0000,0000,0000,,to work out the shortest path
Dialogue: 0,0:44:54.00,0:44:55.00,Default,,0000,0000,0000,,in terms of total weight
Dialogue: 0,0:44:55.00,0:44:58.00,Default,,0000,0000,0000,,from San Francisco to my destination
Dialogue: 0,0:44:58.00,0:45:01.00,Default,,0000,0000,0000,,by a
Dialogue: 0,0:45:01.00,0:45:03.00,Default,,0000,0000,0000,,modified breadth-first, kind of, weighted strategy,
Dialogue: 0,0:45:03.00,0:45:06.00,Default,,0000,0000,0000,,and that is exactly what you're gonna be doing in this assignment. I'm not gonna
Dialogue: 0,0:45:06.00,0:45:08.00,Default,,0000,0000,0000,,give away too much by, kind of,
Dialogue: 0,0:45:08.00,0:45:11.00,Default,,0000,0000,0000,,delving too much in it, but the handout does a pretty good job of talking you through what
Dialogue: 0,0:45:11.00,0:45:15.00,Default,,0000,0000,0000,,you're doing, but it's a, kind of, neat way to think about that's how the GPS, the MapQuest, and things like
Dialogue: 0,0:45:15.00,0:45:16.00,Default,,0000,0000,0000,,that are working is
Dialogue: 0,0:45:16.00,0:45:17.00,Default,,0000,0000,0000,,you're at a site;
Dialogue: 0,0:45:17.00,0:45:21.00,Default,,0000,0000,0000,,you have a goal, and you have this information that you're trying to
Dialogue: 0,0:45:21.00,0:45:24.00,Default,,0000,0000,0000,,guide that search, and you're gonna use heuristics about
Dialogue: 0,0:45:24.00,0:45:28.00,Default,,0000,0000,0000,,appears to be the, kind of, optimal path to, kind of, pick that, and go with it,
Dialogue: 0,0:45:28.00,0:45:31.00,Default,,0000,0000,0000,,and see where it leads you. So
Dialogue: 0,0:45:31.00,0:45:32.00,Default,,0000,0000,0000,,that will be your
Dialogue: 0,0:45:32.00,0:45:40.00,Default,,0000,0000,0000,,task for this week. What we'll talk about on Friday is caching.