Topological Sort

Loading...

En provenance du cours de Princeton University

Algorithms, Part II

713 notes

Princeton University

Algorithms, Part II

713 notes

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms. All the features of this course are available for free. It does not offer a certificate upon completion.

À partir de la leçon

Directed Graphs

In this lecture we study directed graphs. We begin with depth-first search and breadth-first search in digraphs and describe applications ranging from garbage collection to web crawling. Next, we introduce a depth-first search based algorithm for computing the topological order of an acyclic digraph. Finally, we implement the Kosaraju−Sharir algorithm for computing the strong components of a digraph.

Introduction to Digraphs8:30

Digraph API4:56

Digraph Search20:56

Topological Sort 12:54

Strong Components20:22

Rencontrer les enseignants

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science
Kevin Wayne
Phillip Y. Goldman '86 Senior Lecturer
Computer Science

Now we'll look at topological sorting and digraph processing application

that doesn't quite have a parallel with a under record graphs.

And it's a very general module that is very widely used.

And here's a simple example of it called precedence scheduling.

So the idea is that you've got a set of tasks that have to be completed.

But there's precedence constraints.

And you want to know in what order should you schedule the tasks.

So you might think of this as like courses in a university curriculum.

So as a model, we'll use the vertices will be the tasks.

And the edges will be the precedence constraint and

all this says is there's an edge from 3 to 6 that means you have to take

introduction to computer science before you take advanced programming.

And so there is all these sorts of constraints in the graph.

And so what you want is what's called a feasible schedule.

So that's just an order in which you can take the linear order which you can take

the courses one after the other then it respects the precedence.

So that corresponds to drawing the graph such that all the edges point upwards.

And this model is used to study manufacturing processes and

many other applications.

So that's the topological sorting problem.

So first thing is, topological sort works on a DAG, so called DAG,

that's a digraph that has no cycles.

If you have a cycle,

there's no way that you're going to be able to solve the problem.

In fact a simpler graph processing

problem is just to find out if a graph has a cycle.

We'll talk about that in a second but let's do topological sort first, so

we know that the graph has no cycles.

It's a directed acyclic graph, and what we want to do is,

find a way to redraw the DAG so that all the edges point upwards and

give a bottom to top order too, so that all the edges are pointing upwards.

That's called a topological order of the graph.

And that'll give in this case an order in which maybe you could take the courses or

perform the manufacturing process or whatever else.

So that's the problem.

So how are we going to solve it, well we're going to use DFS.

In fact one of the lessons for particularly for

digraph processing is DFS is going to provide a way to solve it,

and might be hard to find a different way.

So, let's look at a demo of topological sort, and

all it is is just run DFS, but there's a particular

point at which we want to take the vertices out, or

to get the order, and that's called reverse DFS postorder.

So let's look at how that works.

What we do is when we do the DFS,

when we're done with the vertex, we put it on a stack or put it out.

So let's look at how that works.

So [COUGH] we had just run DFS, the same as before but

we're not keeping track of anything except the vertices that we're done with.

So vertex 0,

we have to check the places that you can get to from 0 It's 1, 2 and 5.

So we check 1.

1 is unmarked so we are going to mark it and

recursively visit 1.

So we do that, we have to check 4.

And 4 again is unmarked, so we will recurse.

But now, both of the edges to 4 are in, so there's nowhere to go from 4.

So we're done with 4.

When we're done with 4, we output it, actually put it on a stack.

So that's order.

The order in which we're done with the vertices, that's called postorder.

So now, once we're done with four, now, we're done with one.

There's nowhere else to go.

So we put it on the post order.

And now [COUGH] we're back at 0 and

we have to check the other vertices we get to from 0.

So here's 2 and get 2 from 2 and [COUGH] It's unmarked so

we visit it, but there's no place to go so we're done with it,

so we put it on the postorder and go back to zero.

And then we go to five, unmarked so we visit it.

Then we check two, which is marked so

nothing to do, and then we're done with five.

And once we're done with five then we're done with zero and

that's the [COUGH] postorder

the vertices that you get to from zero.

So now we have to check all the other vertices in the graph or

we have to find some other place, and so we just check the vertices in order.

Next one that we find that's unmarked is 3.

And [COUGH] so to visit 3, we have to check 2, 4, 5, and 6.

And 2, 4, and 5 are all marked,

so nothing to do, 6 is unmarked.

So we go visit 6.

When we visit 6, now 0 and 4 are already marked.

So there's nothing to do and we're done with 6 and finally we're done with 3.

We're done with the vertex, we put it out, that's post order.

Or if we put it on a stack, then we get reverse post order.

And that, it turns out, is the answer that we need.

So the code is pretty simple.

But we'll have to look a little more carefully to be convinced that it works.

So it's first search but we have additional data structure

which is a stack of integers which is the vertices in reverse post order.

The constructor just creates that stack and

then the only thing we'd changed to DFS is when we're done with the vertex.

Before exiting we put that vertex on the reverse poststack.

And then the client simply gets the stack returned, and that's an interable.

Iterating through that will give the vertices and

the reverse DFS postorder, which is the top logically sorted order.

It's a very simple and compelling use of DFS.

Actually this is an amazingly simple algorithm but it went undiscovered for

many years, people were using much more complicated algorithms for this problem.

Okay so reverse DFS postorder of a DAG is a topological order.

Now that's the correctness proof that we have to consider.

This diagram over here is a record of the recursive calls for

that example that we just did.

I have to visit zero, we revisit one and then we revisit four and

then we're done with four and then we're done with one and then we visit two.

Done with two, then do five which checks two and down and so forth.

So this gives a record of the calls just for reference in this proof for

that example all right.

So now, we want to consider any edge where v points to w and

we want to consider the point where dfs(v) is called.

And there's a bunch of cases.

One case is that the FSW has already been called and returned.

So in this example, when v equals three,

w equals two, four or five, they were already done.

So [COUGH] if we put out those vertex numbers

before we put three out then the arrow from v to w is going to point up,

they were already done so that's case 1 that's an easy case.

Case two they're all easy cases.

Case two is dfs w hasn't been called yet.

But if there's an edge from v to w, we're going to call it and

then recursive it's going to finish before we're done with 3.

So again, the edge from v to w is going to point up 3 to 6.

And the only other possible case might be that

dfs(w) has already been called, but not returned.

But that can't happen, because there's no cycles.

If dfs(w) had been called but not yet returned,

then the function call stack is going to have a path from w to v on it.

And so if we have an edge vw, that would give a cycle but there's no cycles.

So from those observations, we know that all vertices pointing from three are done

before three is done so they appear after three in the topological order or

they point up if we put the vertices in reverse topological order.

So that's the correctness proof for a [COUGH] topological order.

So a similar process is the detected cycle,

a topological doesn't work if a graphs got a cycle, so

one of the things we might want to do is just find cycles in digraphs.

If you' re a college and you put on the curriculum,

It's gotta direct cycle you have a problem.

So you might want to process that first.

So If there's a directed cycle, you can't have a topological order.

If there's no directed cycle, then we just found it.

So one thing you might want is given a digraph, find a directed cycle.

And how are you going to do that?

You're going to use DFS.

And that's a simple algorithm that you might want to think about.

And it's in a few lines in the book.

So precedent scheduling is an excellent example of

the use of [COUGH] search directed graph.

And this is the cycle of length one.

Of course that requires itself as a prerequisite.

This is just an example of a very widely used computation.

It really has many many applications.

So for example the Java compiler actually does cycle detection.

If you have a class A extends B, and another one B extends C and

another one C extends A.

That's going to create a problem, class hierarchy's not supposed to have cycles,

and it'll actually the Java compiler will actually give a error message saying

there's cyclic inheritance.

You're not allowed to do that.

So there's many applications that involve, essentially,

digraphs that aren't supposed to have cycles.

Another example is Microsoft Excel.

So, if you do a cyclic reference like this in Excel,

which in a big spreadsheet you could imagine might happen.

That's an error.

And not only does Microsoft Excel flag the error,

it says you have created a circular reference, try one of the following.

And it's actually got a circular reference toolbar

that will help you figure out what to do in that case.

So cycle detection and topological sorting are important applications adept for

search and di-graphs.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play