Core: BFS

Loading...

From the course by University of California San Diego

Advanced Data Structures in Java

891 оценки

University of California San Diego

Advanced Data Structures in Java

891 оценки

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

Class design and simple graph search

This week you'll get the backbone of your map search engine up and running. In previous courses, including the previous courses in this specialization, you've probably been given most of the classes you needed to complete the assignments. But learning how to design classes from scratch is a key skill that you will need as you become a more sophisticated Java programmer. This week we'll give you the tools you need to create a robust and elegant class design for your map search engine. We'll introduce a similar problem and show you how it can be represented as a graph. Then we'll introduce two core search algorithms: depth-first search and breadth-first search. Finally, we'll turn our graph problem into a set of Java classes. Your task on the programming assignment this week will be to do the same thing, but in the context on the map search engine!

Core: Intro to Class Design4:48

When I struggled: Building useful classes1:03

In the Real World: Design patterns1:19

Core: DFS, Part 16:14

Core: DFS, Part 24:39

Support: Developing Small Examples to Test Your Code6:40

When I struggled: Data structures jargon1:06

When I struggled: The right data structure for the job1:17

Concept Challenge: Performance of DFS and BFS5:58

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

[MUSIC]

All right.

So, to finish our exploration of basic graph search,

we're going to look at another algorithm called Breath-first search.

So, by the end of this video you'll be able to perform breath first

search on a graph.

You'll be able to implement the code for Breath-first Search,

describe how the ADT (After Data Type) Queue works, and

as well how Queues are used in Breath-first Search.

So, we looked at this algorithm, depth-first search, last video, and we saw

that it would explore all the way to the end of one path before going back and

exploring down a different path.

And the way we made that happen was to use a stack to store where we've been and

where we want to go back to to explore next.

So, that was how Depth- first Search works,

with a stack just like this stack of books.

But in this video let's consider the question.

What if we change just that data structure that we use to figure out

where we've been and where we want to go next?

So, instead of using a stack I want you to consider, what if we use a data structure,

an abstract data type called a queue.

So, the way a queue works is, it's just like a line, say, at a movie theater.

You get in the back of the line, and you come out of the front of the line.

So, in a queue, you're always going to add elements to the back, and

remove elements from the front.

So we're working with two different sides of the list now.

Where as in Stock we are only working with one side of the list and, those

operations, just to get some terminology, are called enqueue, that's adding

an element to the back, and dequeue, that's taking an element out of the front.

We're gonna see that this very small change to this algorithm

Is really going to fundamentally change the behavior of how it searches a graph.

So, let's go ahead and make that change.

So, here's our algorithm.

It's exactly the same pseudocode as I showed you before,

only everywhere I had stack I've now changed that to say queue.

So, those parts in red.

To say queue instead of stack or

the appropriate queue operation, n queue instead of push, d queue instead of pop.

And let's trace this code

on the graph example to see how things are going to behave.

So, just like before we initialize our visited set,

we initialize our parent map which I'm not showing here and

now we're gonna initialize a queue abstract data type so

we put our start into the queue and we mark start as visited.

What do we do next?

Well, now we're gonna enter the loop and we're going to take s off of the queue and

that becomes our current note.

That becomes the note we're currently exploring from and

we're going to explore its neighbors.

We're going to go visit its neighbors.

So, we visit the neighbors.

We visit I and L.

And in visiting them, we do two things, we add them to the queue and

we put them in the visited set.

So, we mark them as visited.

All right.

And then we want to explore some more.

So, we look at the first node in the queue.

The first node in the queue is I.

So, we take I and we explore from I.

At this point we again explore out from the neighbors.

It's only neighbor right now is H, that already hasn't been explored.

If a neighbor's already been explored or visited we won't put it back in the queue.

So, we go to H.

We add H to the queue.

And we mark H now as visited.

My question for you now, is looking at the state of the queue and

where we are in our exploration, what node will be explored next?

All right.

If you said node to L, you'd be right.

Remember, in our queue, we put H in the back, but

the node we're going to take out next is the front.

That node is L.

So, Al is going to become our next current node.

So, what you can see now, you can start to se,

is that instead of going deep down one path, you're going broad out.

So, we explored I, and now we're exploring L, and

our search is going to color the graph in a very broad fashion,

instead of a very deep fashion, like we saw with depth for search.

So let's continue We'll just walk through the rest of this algorithm and

you can see how it's gonna continue to explore outward in the graph.

So, we explore L.

L's neighbor is K.

We mark K as visited.

We put K at the back of the queue.

Next, we take H off the front of the queue and explore from H.

H's neighbor is D.

We put D at the rear of the queue, mark D as visited.

Then we take K off the front of the queue.

We explore from K.

K's neighbor is J.

Put J at the back of the queue.

Mark J as visited.

We go back to D because that's now the front of the queue.

So, we explore from D.

We pick it's neighbor C, put it into the queue, mark it as visited.

we now go to J and don't worry we're almost done.

We now go to J.

We take J as our current node, we explore from J.

We put G into the queue, notice we haven't gotten to G yet,

we know G's our gold node.

But we haven't seen it really yet, we're just scheduling it to be explored by

putting it on the back of the queue So, and we're marking it as visited because we

know we're going to get there, but we don't go to G next.

We go back up to C because that's at the front of the queue.

So, we explore out from C.

We take B, put in at the back of the queue, add it into our visited set.

And only now do we get to go to G and find ha!

Here we are at our goal.

So, as you notice in this example,

this did a very different exploration behavior than depth first search.

And it was just that subtle change of what abstract data type we used

to keep track of the notes that we needed to explore from.

We're gonna end by talking about one example, one way in which depth-first

search and breadth-first search produce actually different results on the graph.

They both can be used to explore a graph, but some things,

some properties of them are going to be a little bit different.

So, one property is going to be that if we explore our graph.

Let's go back to that original graph that we could reach our goal by

going over the top.

And if we look at the path that Depth-First Search found in this path,

we can see that it's fairly long.

It goes over the top but there was a shorter path that we could have found.

And that's just because we got going on this original path that went up and

we ended up finding the goal so we were good enough with that.

But that path wasn't great.

If you look at what breadth-first search does, in fact,

it finds the goal from this much shorter path across the bottom so

this is something that Leo is going to explore in much more detail

next week when we start to really dig in to these graph algorithms.

But for now, we're gonna switch gears and

start talking about how to actually design Java classes for this graph problem.

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

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

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

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

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

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