Core: Implementing graphs in Java

Loading...

来自 University of California San Diego 的课程

Java 高级数据结构

897 个评分

University of California San Diego

Java 高级数据结构

897 个评分

课程 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, we're ready to implement graphs.

Now that we have their definitions and

some of the motivations behind the graphs out the way.

Let's thinks about how to write some classes to describe graphs in Java.

And so by the end of this video, you'll be well on your way to doing just that.

So, thinking back to what we have to represent in our code.

We have the basic objects, which are the nodes or the vertices, and

then we wanna talk about relationships between them.

But now we have to translate everything into

object that the computer can actually manipulate and work with.

And so we're going to represent our vertices as integers.

And so each vertex is going to be named by some integer.

It's going to be a non-negative integer, zero through some number.

And then we can talk about the relationship between those integers

as those edges.

And so let's start building up our class.

And remember that little icon that we've been using throughout the whole

specialization to indicate a class definition.

And so for our class we're going to have to keep track in a given graph,

how many vertices we have and how many edges.

And so those are going to be our private number fields, and

then as we build up a graph and add more vertices, add more edges we're going

to want to be able to have access to those key properties that we care about,

the number of vertices, the number of edges,

that as we said before will determine the size of the graph.

We need both of those components.

We're going to start by saying any graph needs to tell us information about that.

Now notice that the class that we're defining right now is an abstract class.

And in the abstract class what we're doing is we're saying some data

that's associated with any graph and

some methods that ought to be available whenever we have a graph.

But we're going to leave some of the implementation not completely specified

and we're going to leave it to our subclasses to specify

how we implement some of the key functionalities of the graph.

So, in particular for a graph, we're going to want to add vertices, and

so any graph ought to be able to do that.

So we have a method in our abstract classes says,

we ought to be able to add a vertex.

And notice that there's no arguments to this method because what we're going to do

is just say, however many vertices we have now, those have certain indices.

Now, add a new vertex, and just give it the next available index.

And, how do we do that?

How do we represent vertices?

We'll that's going to be an implementation detail

that's decided by the subclass that we'll write a little bit later.

And so as part of our addVertex method,

the first thing we do is we're going to call the implementAddVertex method,

that at this point we're going to leave abstract.

We're going to say whichever class fills in the specification,

fills in the implementation, will have to tell me how to implement adding a vertex.

But, any graph ought to be able to do that.

And as soon as I've implemented add the vertex,

then I need to increment my count of how many vertices there are by one.

Okay, now we're gonna do a similar process for adding edges, and for our abstract

class definition, we're going to specify that we need at least one other method

that should be available when we have a graph, and that's the getNeighbors method.

Now, why is that important?

Why do we care about getting neighbors?

The reason we have a graph is not just for the nodes and

thinking about them as objects but we care about the relationships, and

so if we have a particular node that we're trying to think about then

we wanna know which vertices are adjacent to it.

And thinking back to the project,

thinking back to the application that we care about.

If our nodes are cities then what we'd like to know is, which other cities

could we get to just by following a single road, or if our edges represent

airplane routes then which cities can we get to just using a non-stop flight.

So the getNeighbors method is a really important method that we would like to

implement in our graph.

And so what our next step will be is thinking about the subclasses that we'll

define in Java to fill in some of those abstract methods and

in particular to make decisions about how to represent our vertices and our edges so

that we know how to implement those methods.

探索我们的目录

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

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

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

通过 App Store 下载

通过 Google Play 获取