Support: Coding getNeighbors

Loading...

From the course by University of California San Diego

Advanced Data Structures in Java

880 оценки

University of California San Diego

Advanced Data Structures in Java

880 оценки

Course 3 of 5 in the 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.

From the lesson

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

Meet the Instructors

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

[SOUND] All right, in this support video, we're gonna write some code.

Mia has talked to you about two ways of representing a graph,

using an adjacency list, and using an adjacency matrix.

And she's also talked to you about the out degree of the vertices in a graph.

So, in this video what we're going to do is we're actually going to write a method

where we get all of the nodes that are one degree one hop away

from a particular node in the graph.

And we'll be writing this code for

both an adjacency matrix as well as an adjacency list representation.

So, by the end of this video, you'll be able to write this code.

We're gonna do it together.

Not actually in Eclipse.

We're just gonna write it out on these slides.

And the reason I'm choosing to write by hand, rather than write in the code in

Eclipse is that sometimes when you're writing on paper, or on a tablet computer.

You're a little bit more thoughtful about what it is that you're doing.

Because you're not able to run the code and test it.

So, that's why I'm gonna show you this code written out on a tablet.

All right, so lets review the Adjacency Matrix Representation for the graph.

As you may recall there's a row for every vertex in the graph, so

these rows correspond to vertices 1, 2, 3, 4 and 5.

5 and then, in each row there's a 0 in the entry if there's no edge from that vertex

to the vertex represented by the column, and there's a 1 if there is an edge.

So for example, if we look at this edge right here,

we can find that 1 for that edge in row 2.

Go over here to entry 3 and there's our edge.

There's a 1 there.

And 2 doesn't have edges anywhere else, so there are no other 1's in 2's realm.

So, we're going to use this information to write the get neighbors method

in our graph representation.

So, we've got the start of our graph representation there on the screen,

we've got our matrix representing the edges in the graph.

And our goal now is to write get neighbors.

So, let's go on and actually do the writing.

Although before we do, let's actually go back for one second and look at this graph

and think about, how can we tell what nodes are neighbors of a particular node.

Well, all we really need to do is we need to look at the row.

So, we just look at this row right here, and if there's a 0 in that entry, then,

it's not a neighbor.

But if there's a one in the entry, then it is a neighbor, and that's the essence of

the algorithm that we're going to use to implement in our method.

So, here's the header for our gate neighbor's method.

We're going to return a list of integers, and

that list of integers is going to contain all the vertex integers

that our neighbors of the particular node that we pass in.

So, we're taking an int v, which is a vertex in our graph, we're gonna return

the integers representing all the neighbors of that vertex.

So, let's get started.

Well, what's the first thing that we need?

We need to return a list, so we're going to need to have a list to return.

So, let's go ahead and create that list.

And I'll make my list an array list.

Okay, now we've got our list, and

we're just gonna implement that algorithm just like I described.

V is going to be the row of the adjacency matrix that we're looking at.

And then, we're just gonna iterate all the way through that row, looking for

the ones and adding them to our list to return when we find them.

So, we're gonna need a loop.

Our loop is going to go as long as I is less than the number of vertices in

the graph.

So, I should be less than, and I'm saying here we have this getNumVertices method

already defined for us.

So, I will be less than getNumVertices and then, i plus, plus.

All right.

So now, what we need to do,

we need to check the entry in the particular row that we're looking at,

figure out if it's a one, and if it is, we'll add it to our list to return.

And, in fact, I'm gonna look to see if it's a 0, and if it's not a 0,

then I'll add it to the list just in case somebody's using some non-zero value to

represent an edge, like a weighted edge.

So, if my adjacency matrix

in row v at position I is not

equal to 0, then I will add

It to my neighbor's list.

And that's all I need to do, that'll collect all the neighbors of v and

then at the very end of course I need to return the neighbors.

Oops.

And that's it, that's our implementation of get neighbors for our adjacency matrix.

So, let's now look at the implementation for an adjacency list,

here's our adjacency list representation of the very same graph.

So, let's look at how this works,

we have basically a map that's going to map the integers,

which are the vertices in the graph, to a list of all of their neighbors.

Okay, so you might be thinking, this is actually pretty tricky reveal,

all we need to do is look up the index we're looking for and

return the list of neighbors, and you'd pretty much right.

It really is almost that simple.

So, here's again our method header, we return a list.

So, now I can just, one idea,

is that I can just return the adjacent C list.

Map, that's this variable right up here.

So, I'll turn adjacency list map.get to get the index v.

So, is it really that simple?

Is that all I need to do?

Take a minute and think about that.

Is that an implementation that'll solve this problem?

Alright, now that you've thought about it,

well the answer is yes, and well not quite.

Yes, it actually does return a list of neighbors of the particular node v that

we're looking for.

But the danger is, it returns the list of neighbors that we're using for

internal storage inside our graph.

We've just exposed this list

that's supposed to be internal to our graph representation.

So, anybody out there can now modify this list and change our graph.

Structure, and we don't want that to happen.

So, we can fix this problem by instead of returning the list that we take right out

of this hash map and return it to the user, we can return a copy of this list.

So, instead of just returning the list directly,

let's just change it slightly so that we return a new list

And we can pass it in the thing that we were returning before.

That implementation there is just a little bit safer than what we originally had.

Both will return the correct list, but

one will protect the private data inside our graph.

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

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

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

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

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

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