[MUSIC] So, this whole course is going to focus on a new data structure called graphs. And what we're going to do in this video is introduce the idea of graphs and why we even need such a data structure. So, by the end of this video, you'll be able to explain why this abstract data type is useful and compare this graph abstract data type with the other ones that you're probably familiar with. So, let's think back to the data structures and the abstract data types that you've worked with already. We may have collections of object that really don't have links between them and don't have a lot of structure at all. So, we might organize these objects into a set, which is basically just a collection of these things. But often, when we're organizing our objects, we like to have them in some sort of sequential order. And so arrays and linked lists let us organize the object that we're talking about in a line, one after the other. And so we can do things like, traverse that list, iterate over it, search by index, for example. And pick out element in that ordered list of objects. But in the previous course, we had applications where there was a hierarchy amongst the objects that we were organizing. So, you can think back to organizing dictionaries of words. And when those dictionaries of words, there was common structure in those words. For example, we could have one word that's a prefix of another word. And so we want our data structure to mirror that common structure. And trees are really great for that, because you can indicate when nodes are connected to one another. And in this tree structure, we have that one node is a parent of another node if that parent is a prefix of its child. And so we could organize our data structure in this way and have the nodes be linked by this prefix relationship. And so in all of these different view points and all of these different applications, what we're thinking about are these objects and then whether they have some explicit connections between them. So, we have these basic objects and their relationships. And that's really at the heart of what we need when we are talking about graphs. So, graphs really generalize this principle of organizing a whole lot of objects together so that we have objects and relationships between them. And now we wanna think more generally about what kinds of relationships we might have. So, really, when we define a graph, what we need to do is define those basic objects, and those relationships. And those basic objects are depicted in our representation of a graph as vertices, or nodes. And so each object is one vertex in our graph, also known as a node, and we draw that pictorially as a circle. And then when we want to denote a relationship between two vertices, or two nodes, then we can draw an edge between those vertices, or an edge between those nodes. And those edges sometimes are called arcs or links. So, let's think about where we might use these graphs. So, if we wanna think about objects that are related to one another, a really good example is the Internet. And we have in this internet, all sorts of websites. Each of us can create our own website, write up some HTML code, upload it to some server, and maybe connect it to other websites using hyperlinks. And so we can imagine and visualize this entire internet as a graph where each of the basic objects the vertices in our graph are the websites. And then there's an edge between two websites if there's a link that connects them. Now, there's other contacts in which we have objects that are related to one another. And we can think about in the physical world, when we want to connect up to a cell phone network, and we can think about the coverage of the network depicted by a graph. And so we wanna represent the coverage of that cell phone network across the whole city, and that's going to be determined by which towers have overlapping coverage areas. And so we can imagine a graph whose vertices are the cellphone towers and then there's an edge between two cellphone towers in their coverage area overlaps and so they could hand off a call to one another. But we could also think about a different situation in which we have basic objects and relationships. And this situation could map something much more sociological. So, we could imagine that the basic objects are people, real live people in the world. And the relationship between people could be a friendship relationship. And so we could imagine a huge graph, where each node on the graph is a person, me, you, each one of us is a node on this graph. And then there would be an edge between two of us if we were friends with one another. And so you could imagine the questions that we could ask about this graph that would tell us how communities are formed and evolve in the world that we live in. And these social networks as just a quick peek are what we'll be focusing on in the cap stone project for the specialization. So, stay tuned for those. But for now, we're actually going to think about a different graph for this courses project. And this graph is more geographic. So, we can think about a graph that represents how we move around in the world. So, our basic objects in this graph could be cities or locations in the world. And then, we might want to go between one city and another. And so, the relationships between cities could be, for example, a non-stop flight. And so if you've been in a plane and you've flipped through the seat back magazine, there's often a picture of all the flight paths of that particular airline. And you see that there's edges between two cities if there's a nonstop flight offered by that airline between those two cities. And so then we can think about this graph is telling us information about how to plan a route throughout the world. So, we'll talk a lot more about that in the project. But I wanna mention that if we think away from the flight context, there's more than one way to get between two cities. So, for example we could think about driving, having a road trip between one city and another. And so we could have a graph that is richer than just the flight plan and have different kind of edges for different ways of transportation between the two cities. So in our graph we might have multiple edges between two nodes, between two vertices. All right. One more example. We could have a graph where the basic objects aren't physical things. They're not cities, they're not people, but rather they're tasks. So, think about a big complicated project that you might want to produce perhaps with a big team. And in this project there's lots of individual tasks. So, maybe it's a software engineering project. Maybe it's a big cooking project. It doesn't matter. It's a really big project. That is split up into small tasks. But some of those tasks require another task to be completed before we start it. And so there's relationships between certain ones of those tasks which are dependency relationships. And so we can picture those relationships in a graph where we have the vertices are the tasks. And then we have an edge from one task to another if we need to complete that first task before we go on to do the second one. And then what's useful about having this dependency graph is that then that let's us do is solve the scheduling problem. How do I take all of these tasks and put them in order so that I can complete my project successfully while respecting the dependencies? So, these graphs are super powerful. It's a really general notion that can be used and manipulated to represent a lot of different problems. And so if we think more generally about the problem that we have, in each of these cases, we're asking some questions about a graph. And then afterwards Christina and Leo are gonna come back and think of how do these general questions actually map down to the concrete root planning that we want to do in the project. So, for graphs in general, we want to create a graph. We wanna ask about two vertices in the graph. Are they close, are they far? Is it possible to get from one to the other? We can ask also global properties of the graph. Are there lots of edges? Are there lots of relationships? Are things tightly woven together? Or is it a pretty sparse graph? And then we can also ask about can we break up the graph into connected components, different pieces. Are there pieces that really don't attract much with one another or is everything really intertwined? Are there paths between every two vertex? Every two vertices. So, we'll be thinking about each of these questions, but before we do that, first of all, we have to define the graph, so that's what we'll do next.
