Topological Sorting & DFS

Go to:
> Material
> Lecture Recap

Material

• Slides: pre-class (w.o. solutions)
• Slides: with solutions & annotations
• Code:
  • graphTraversal - problem statement, Java CodeExpert template & test-cases
    • Copy the contents of the Main, custom.in and custom.out files into the corresponding files of the ”Welcome” exercise. You can run the tests by using the play button (not the flask).
  • solution

Lecture Recap

This week we look at Directed Graphs, Topological Sortings and Depth-First Search (DFS).

Directed Graphs and Topological Sorting

In contrast to undirected graphs, the edges of directed graphs have a direction: $(u,v) \neq (v,u)$. This quite naturally allows us to model dependency relations between vertices. A problem that then often comes up in practice is to ask for an order that satisfies all dependencies among a set of tasks. This, as we saw this week, can be modeled as the problem of finding a topological sorting of a directed graph $G = (V, E)$, i.e., a linear (total) ordering of vertices $v_1, v_2, \ldots, v_n$ such that: $(v_i, v_j) \in E \implies i < j$. In other words: all edges point “forward” in the ordering.

• Theorem: A directed graph $G=(V,E)$ has a topological ordering if and only if $G$ is acyclic (a DAG - Directed Acyclic Graph).

Proof idea: Acyclic graphs always have a sink (vertex with no outgoing edges). We can recursively place sinks at the end of our ordering. More efficiently, DFS gives us the ordering directly: reverse post-order produces a valid topological sort.

Depth-First Search (DFS)

DFS explores graphs by going as deep as possible before backtracking, keeping track of which vertices have already been visited. It runs in $O(|V| + |E|)$ time and is a very versatile algorithm.

Some applications:

• Cycle detection: A graph contains a cycle if and only if DFS finds a back edge (for undirected graphs: an edge to a visited vertex that isn’t the parent)
• Reachability: Run DFS from source $u$ to check if target $v$ is visited
• Connected components: Count how many times we start a new DFS from an unvisited vertex

In this week’s coding exercise, you’ll implement all three algorithms using DFS!