CSCE 411 Lecture 18

Lecture Slides

« previous | Friday, October 5, 2012 | next »

Depth-First Search (DFS) Cont'd

Topological Sort

Given a directed acyclic graph (DAG), find a linear ordering of the nodes such that if $(u,v)$ is an edge, then $u$ precedes $v$.

DAG edges indicate a precedence or dependency.

Perform DFS, and either

1. insert vertices at front of list as recursive call finishes or
2. sort all vertices by finish time

Example

Tasks that have to be done to eat breakfast:

get glass, pour juice, get bowl, pour cereal, pour milk, get spoon, eat.

Precedence:

eat breakfast
  |-- pour juice
  |   `-- get glass
  |-- pour milk
  |   `-- pour cereal
  |       `-- get bowl
  `-- get spoon

DFS traversal has following discovery and finish times:

1 2 3       4 5 6 7 8 9       10 11 12 13        14
| | '--eat--' | | | | '--milk--'  |  |  '--spoon--'
| '---juice---' | | '---cereal----'  |
'-----glass-----' '------bowl--------'

When each node's recursive call finishes, insert it on the front of a list:

spoon, bowl, cereal, milk, glass, juice, eat

(or just sort by finish time)

Correctness

3 Cases for $u$ precedes $v$:

1. $v$ is finished when $u$ is discovered, then $v$ finishes before $u$.
2. $v$ is not yet discovered when $u$
3. $v$ is discovered but not yet finished will not happen on an acyclic graph.