Graph Algorithm #1: Topological Sort - University of Washington

Lecture 20: Topo-Sort and Dijkstra¡¯s Greedy Idea

? Items on Today¡¯s Lunch Menu:

? Topological Sort (ver. 1 & 2): Gunning for linear time¡­

? Finding Shortest Paths

? Breadth-First Search

? Dijkstra¡¯s Method: Greed is good!

? Covered in Chapter 9 in the textbook

R. Rao, CSE 326

Some slides based on: CSE 326 by S. Wolfman, 2000

1

Graph Algorithm #1: Topological Sort

322

143

321

326

142

Problem: Find an order in

which all these courses can

be taken.

Example: 142 143 378

370 321 341 322

326 421 401

R. Rao, CSE 326

370

341

378

421

401

2

Topological Sort Definition

Topological sorting problem: given digraph G = (V, E) ,

find a linear ordering of vertices such that:

for all edges (v, w) in E, v precedes w in the ordering

B

C

A

F

D

E

R. Rao, CSE 326

3

Topological Sort

Topological sorting problem: given digraph G = (V, E) ,

find a linear ordering of vertices such that:

for any edge (v, w) in E, v precedes w in the ordering

B

C

A

F

D

Any linear ordering in which

all the arrows go to the right

is a valid solution

E

A

R. Rao, CSE 326

B

F

C

D

E

4

Topological Sort

Topological sorting problem: given digraph G = (V, E) ,

find a linear ordering of vertices such that:

for any edge (v, w) in E, v precedes w in the ordering

B

C

A

Not a valid topological

sort!

F

D

E

A

B

E

C

D

R. Rao, CSE 326

F

5

Topological Sort Algorithm

Step 1: Identify vertices that have no incoming edge

? The ¡°in-degree¡± of these vertices is zero

B

C

A

F

D

R. Rao, CSE 326

E

6

Topological Sort Algorithm

Step 1: Identify vertices that have no incoming edge

? If no such edges, graph has cycles (cyclic graph)

B

C

A

Example of a cyclic graph:

No vertex of in-degree 0

D

R. Rao, CSE 326

7

Topological Sort Algorithm

Step 1: Identify vertices that have no incoming edges

? Select one such vertex

Select

B

C

A

F

D

R. Rao, CSE 326

E

8

Topological Sort Algorithm

Step 2: Delete this vertex of in-degree 0 and all its

outgoing edges from the graph. Place it in the output.

B

C

A

F

D

E

R. Rao, CSE 326

9

Topological Sort Algorithm

Repeat Steps 1 and Step 2 until graph is empty

Select

B

C

F

D

R. Rao, CSE 326

A

E

10

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download