Core: Neighbors

Loading...

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

Advanced Data Structures in Java

920 оценки

University of California San Diego

Advanced Data Structures in Java

920 оценки

Курс 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]

All right, so we're ready to bring together some graph properties and

implementation decisions and see the trade-offs between them.

By the end of this video, you'll be able to implement

a method to talk about the neighbors of a vertex in two different ways.

Each of those ways depending on the implementation that we have for

the graph structure.

Now, what will you want to do in this video,

is think about the ramifications of the decisions of the implementation.

And then how do we build other features of the graph, based on those implementations.

Now you'll see more details of the Java code in a support video

that comes along with this, and so stay tuned for that.

All right, so let's think about what the notion of neighbor is really getting at.

And we have our graph example that we've been working with.

This is just our toy six-vertex example.

And if we want to think about a neighbor in this graph,

we're talking about the relationship between one vertex and other vertices.

And so a neighbor of a vertex is a vertex which is adjacent to that one.

And adjacent here means that there's an edge between them.

And so let's focus in on vertex 4 over here, and

ask which vertices are adjacent to 4?

Now we can see that there's two edges that are related to 4 in some way.

There's one outgoing edge and one incoming edge.

And so if we drop the directions altogether, then both of the vertices 3

and 5 seem to be related to, or adjacent to, or connected to 4 in the same way.

But for directed graphs, where we're going to tease apart the relationship the 3 has

to 4 from the relationship that 5 has to 4.

And so let's focus on the relationship between the vertex 5 and the vertex 4.

And we notice the vertex 5 is the start point of an edge that ends at 4.

And so we can talk about the in degree of the vertex 4 as the number of

incoming edges to that vertex.

And so then, in order to look at all of the neighbors of 4,

that are neighbors by virtue of being the star point of edges that end at 4.

We want to count all of the incoming edges to 4.

We want to count the in degree of that vertex.

We could also talk about the out degree of the vertex.

We could talk about all of the vertices that we can get to from starting at 4 and

just going by one edge over to a new vertex.

And so, for example, from 4 we could follow the edge to 3.

And now let's start actually thinking about methods to implement

finding these in degrees and out degrees.

So for the out degree, what we're trying to do is count all of the edges that

are outgoing from the vertex 4.

And one of our representation for graphs is the adjacency matrix representation.

So we have a grid of 0's and 1's, and we have as many rows as there are vertices,

we have as many columns as there are vertices.

And each entry in the adjacency matrix denotes an edge

which starts at the row vertex and ends at the column vertex.

And so if we're looking at the number of outgoing edges from the vertex 4,

we just need to look into that fourth row of the matrix and

see how many edges start at vertex 4.

Namely how many 1s are in that row of the matrix.

And so we can go along and see that's there's exactly one 1 and so

our out degree is 1.

All right, we had another representation of graphs as well.

A representation in terms of the adjacency list.

And so in the adjacency list representation we have

a list that's associated with every vertex.

And so for the vertex 4 we have a list that contains just 3 and

what that denotes is that there's an edge that starts at 4 and goes to 3.

And so if we're looking at how many edges start at the vertex 4,

what we need to know is the size of the list

that's associated with 4 in the adjacency list representation.

And so now, what do you think?

Which of these representations of graphs makes it easier, or more efficient,

to find the out degree of a vertex in the graph?

All right, welcome back.

Let's now ask the flip question and think about the in degree of a vertex.

So if we're thinking about the in degree of the vertex 4.

In the adjacency matrix representation things are very symmetric, and

the incoming edges are just denoted along columns instead of along rows.

And so if we want to think about the number of incoming edges to 4, we need to

read off that fourth column in the matrix and look for 1s in that fourth column.

Each one of those 1s has four as its endpoint, but

in the adjacency list representation we have a slightly different situation.

Our markers are indices for which lists we have in the adjacency lists

representation are the starting point of edges.

And so if we're looking for the incoming edges to 4,

what we need to do is look at each one of the lists in the adjacency lists

representation, and ask which one of those lists contain the vertex 4?

Because a list contains the vertex 4 that means

the 4 is the end point of the corresponding edge.

All right so we have two different representations,

which one makes computing the in degree of a vertex more efficient?

All righty now what's next?

We've talked about in degrees, we've talked about out degrees we've seen

how they both contribute to this notion of a neighbor of a vertex.

And now what we're ready to do is implement some of these notions in Java.

So in this week we're focusing on the differences in performance based on

implementing graphs using a JSON-c matrices and a JSON-c lists.

And then in future weeks, you'll build even richer class structures for

representing graphs.

And you'll wanna take these performance considerations into account

as you're building these more complicated structures.

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

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

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

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

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

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