Topological Sorting

A topological ordering of a directed graph G is a labelling f of G's nodes such that:

1. the f(v)'s are the set {1,2...n}
2. if (u,v) belongs to G -> f(u) < f(v)

Use: When creating sequence tasks while respecting all precedence constraints.

It should be an acyclic graph. Running time: O(m+n).

Example

Topological sort via DFS

• Follow the out-going arcs from a node
• Once you've reached the end, backtrack!
• Label nodes along the backtrack path if they have no more out-going arcs else follow the arcs
• If you meet an explored node on the way, ignore it!

Algorithm

DFS_loop(graph G)

- mark all nodes unexplored

- current_label = n    

- for each vertex v in G

  - if v not yet explored

    - DFS(G, v)

DFS (graph G, start vertex s)

- mark s as explored

- for every edge (s,v):

  - if v unexplored

    - DFS (G,v)
- set f(s) = current_label
- current_label --