Topological Sorting

Document last modified: 

Overview

Topological sorting is useful for defining the order things must be done. For example, prerequisites must be completed prior to certain other courses.

DAG (directed acyclic graph) can model the problem (what is a cycle?) and the DFS can produce a sort that defines one valid ordering of paths to follow.

Question 22.16

Topological sort

Example

The following is a DAG at left that has been topologically sorted at right. It shows one valid ordering: DEABC.

Other valid orderings are possible from the DAG, for example: ADBEC

Question 22.17 - Which of the following are invalid orderings and why?

  1. ADEBC
  2. CBAED
  3. ABCDE
  4. DECAB

Example - Cormen page 613

A = {belt, jacket, pants, shirt, shoes, socks, tie, undershorts, watch}

R = {(a, b): a, b ∈ A 

a R b = { if a is on, won't have to take a off to put on b }

R = {(belt, jacket), (tie, jacket), (shirt, belt), (pants, belt), (pants, shoes), (shirt, tie), (undershorts, pants), (undershorts, shoes), (socks, shoes)}

Topological-Sort (G)
1 call DFS (G) to compute the v.f  for each vertex v
2 as each vertex is finished, insert it onto the front of a linked list.
The last finished is at the head of the list.
3 return the linked list of vertices, which is sorted last to first finished

Start with shirt.

Question 22.18

  u v w x y z
Π NIL u NIL y v w
d 1 1 9 4 3 10
f 8 7 12 5 6 11

DFS (G)
       -- Initialize arrays
1 for each vertex uG.V do
2    u.color ← WHITE
3    u.Π ← NIL
4 time ← 0
5 for each vertex uG.V do
6     if u.color = WHITE then
7        DFS-Visit (G, u)
DFS-Visit (G, u)
1       u.color ← GRAY
2 timetime + 1
3 u.dtime
4 for each vertex vG.Adj[ u ] do
5    if v.color = WHITE then
6       v.Π ← u
7       DFS-Visit (G, v)
8 u.color ← BLACK
9 u.ftime time + 1

 

 

Ordering of Values in Sets