Support: Coding 2-Hop Neighbors

Loading...

来自 University of California San Diego 的课程

Java 高级数据结构

899 个评分

University of California San Diego

Java 高级数据结构

899 个评分

课程 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

[APPLAUSE] >> All right, in the last

support video we looked at code for finding the one-hop neighbors for nodes

in graph that's represented as adjacency list as well as in adjacency matrix.

But in your assignment you're going to have to write some code to generate

the two-hop neighbors, so all the neighbors you can reach and

not just one edge hop, but two edge hops.

So what we're gonna do in this support video is give you some

help with that task.

Now spoiler alert.

This is going to give away most of the code that you'll be writing in this part

of the assignment, but it's also going to introduce you to a really cool trick for

doing matrix multiplication for finding these two-hop neighbors.

So if you don't want the spoiler of the code, but you just want that cool trick

about the matrix multiplication you can jump to part two of this video.

So by the end of these two parts you'll be able to write the code for

generating the two-hop neighbors in both the adjacency list implementation as well

as the adjacency matrix implementation of a graph.

And you'll also be able to describe how matrix multiplication in an adjacency

matrix representation can generate the two-hop neighbors for

all of the nodes in the graph.

So lets get started.

Let's go back to our graph representation.

Here's a graph.

It's a fairly simple graph that you can see here.

That's the graph example that we're going to be working with in these two videos.

So our problem again on the assignment is to write a method

that given a vertex say vertex 0 comes back with a list of

all of the neighbors that you can reach in two hops.

So not one, but two hops away.

So if we start with that vertex 0 we can see that

well we can't reach node 0 in two hops, but we can reach node 1 in two hops.

We go down through node 2 and then up to node 1.

We can't reach node 2 in two hops.

We can only reach it in one because two hops and we go away from node 2, but

we can reach node 3, and in fact we can reach node 3 in two different ways.

We can go through node 2 down through the bottom, or we can go through node 1 up

across the top, so there are two different paths from 0 to 3.

So that's the problem that we're working with.

Now our solution is going to be similar, but

slightly different depending on our graph representation.

So let's get started right away with our adjacency list representation.

So here's our adjacency list representation of this graph.

You can see that each node is an entry into this map, and

the values of the map are just the lists of connected vertices.

So we looked at the code for

finding the one hop neighbors in the last support video, and it looked like this.

And we saw that this code was actually almost trivial.

It was extremely easy to find the one-hop neighbors using the adjacency list

representation.

Turns out that finding the two-hop neighbors is really not that much more

complicated.

So what you're going to do to find these two-hop neighbors is well

you've already got a way to find the one-hop neighbors.

Here it is.

So instead of just returning the one-hop neighbors all you need to now do is

from each of the one-hop neighbors just loop through them and

find their one-hop neighbors.

So the one-hop neighbors of the one-hop neighbors are the two-hop neighbors of

the original node.

So that's a pretty big start on your two-hop neighbor implementation for

your adjacency list representation of your graph.

So next let's go on to consider how you would do this for an adjacency matrix.

So before we do that I want you to take a minute pause, and

actually draw the adjacency matrix for this graph example here.

All right welcome back.

Hopefully this is the adjacency matrix that you came up with.

You know that each row corresponds to neighboring vertices in the graph, so

for example in row 0 we have a connection to vertex 1 and vertex 2,

because we have edges from vertex 0 to vertices 1 and 2, but not to 0 and 3.

Now let's look again at the code for

generating the one-hop neighbors in this adjacency matrix representation.

It was a little bit more complicated than the code for

generating the one-hop neighbors in the adjacency list presentation, but

it wasn't terribly difficult either.

So what we did is we went to the row V for the vertex that we're looking for, and

then we just looped through that row, and for every entry that we found

that was greater than 0 we knew there was an edge to that vertex.

And so we added it to our neighbors list, and

in the end we just returned the neighbors list.

That's the code that we looked at, but

if you look at the starter code what you are going to find

is that the code looks just a little bit different so it actually looks like this.

So there's a change.

Instead of that if statement we now have an inner loop, and that inner loop starts

at 0 and it goes up to the value stored in the adjacency matrix at position v i.

So my question for you that I want you to think about is what is this change doing?

All right.

So you see that we made this change.

What in the world is this about?

Well it seems like what we're doing is we're going into the adjacency matrix, and

we're getting the value there and

if that value is 1 we'll only add the neighbor once, but

if that value is greater than 1 we're going to add that neighbor multiple times.

So the question becomes why would the value in the adjacency matrix ever be

greater than 1, and the reason is when we have multiple edges between nodes.

So it's entirely possible the node graph we actually have two edges between

say node 0 and node 1 in this case.

And so the way we're gonna represent that in the adjacency matrix is we're just

gonna change the value of that entry to represent the number

of edges between that pair of nodes.

So in this case we'd have a two between the vertices 0 and 1.

And you'll see that this actually does happen in our row data, so sometimes

there's a street that actually just makes a loop and there's an intersection here

and an intersection here, and you can get from this intersection around this way and

this intersection around that way, and we have two edges between those two nodes.

So this is real world data here.

And so what we want to do is for get neighbors is we want to count each

neighbor the number of times that we can get to it from a particular node, so

because we can get to vertex 1 twice following two different

edges from vertex 0, vertex 1 is gonna go into that neighbors list twice.

We're going to maintain this convention in our get two-hop neighbors, so

if you can reach a two-hop neighbor via two different pods

it's going to go into the two-hop neighbor's list twice.

So let's go back to this original example that we were working with and talk about

how to turn this get neighbors method into a get two-hop neighbors method.

And again it's pretty straightforward.

We already have the code that gets the one-hop neighbors, so

now instead of just adding i as we did for the one-hop neighbors

to our list to return what we want to add instead is the neighbors of i.

The one-hop neighbors of i, and

if you think about it you actually already got some code that will do that for.

So it's just a matter of calling a method that already exists.

So again here's your spoiler.

This is a lot of the code that you're going to need in order to solve this part

of the assignment.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2018 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取