Core: What's a graph?

Loading...

Из курса от партнера University of California San Diego

Advanced Data Structures in Java

957 оценки

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

University of California San Diego

Advanced Data Structures in Java

957 оценки

Курс 3 из 5 — Specialization Object Oriented Java Programming: Data Structures and Beyond

How does Google Maps plan the best route for getting around town given current traffic conditions? How does an internet router forward packets of network traffic to minimize delay? How does an aid group allocate resources to its affiliated local partners? To solve such problems, we first represent the key pieces of data in a complex data structure. In this course, you’ll learn about data structures, like graphs, that are fundamental for working with structured real world data. You will develop, implement, and analyze algorithms for working with this data to solve real world problems. In addition, as the programs you develop in this course become more complex, we’ll examine what makes for good code and class hierarchy design so that you can not only write correct code, but also share it with other people and maintain it in the future. The backbone project in this course will be a route planning application. You will apply the concepts from each Module directly to building an application that allows an autonomous agent (or a human driver!) to navigate its environment. And as usual we have our different video series to help tie the content back to its importance in the real world and to provide tiered levels of support to meet your personal needs.

Из урока

Introduction to Graphs

This week we'll start getting technical, introducing you to the central data structure in the course: Graphs. You'll learn the basics and then have a chance to dive in a little deeper into the code, getting ready to start building that Google Maps-like application.

Core: What's a graph?8:30

Core: Graph definitions4:34

In the real world: Graphs at Google2:50

In the real world: More graphs at Google0:55

Core: Implementing graphs in Java3:55

Core: Adjacency matrix12:23

Core: Adjacency list7:43

Concept Challenge: Comparing implementations of graphs3:58

In the real world: Performance considerations2:23

When I struggled: Analyzing implementations0:47

Core: Neighbors5:45

Support: Coding getNeighbors7:30

Support: Coding 2-Hop Neighbors7:18

Support: Multiplying Adjacency Matrices4:02

Познакомьтесь с преподавателями

Leo Porter
Assistant Teaching Professor
Computer Science and Engineering
Mia Minnes
Assistant Teaching Professor
Computer Science and Engineering
Christine Alvarado
Associate Teaching Professor
Computer Science and Engineering

[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.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play