§ DFS and topological sorting

The proper way to solve a maze is to keep breadcrumbs! Use recursion. Recursively explore the graph, backtracking as necessary.

§ DFS on a component:

parent = { s: None}
dfs-visit(adj, s):
  for v in adj[s]:
    if v not in parent:
      parent[v] = s
      dfs-visit(adj, v)

§ visit all vertices:

dfs(vs, adj):
  parent = {}
  for s in vs:
    if s not in parent:
    parent[s] = None
    dfs-visit(adj, s)

§ Complexity

We call dfs-visit once per vertex $V$. Per vertex, we pay adj(v) per vertex v. In total, we visit |E|.

§ Shortest paths?

DFS does not take the shortest path to get to a node. If you want shortest paths (in an unweighted graph), use BFS.

§ Edge classification

1. Tree edges : visit a new vertex via that edge. Parent pointers track tree edges.
2. forward edges : goes from node n to descendant of node n.
3. backward edges : goes from a node n to an ancestor of node n.
4. cross edges : all other edges. Between two non-ancestor-related nodes.

How do we know forward, back, cross edges?

§ Computing edge classifications

• backward edges : mark nodes being processed. if we see an edge towards a node still being processed, it's a backward edge.
• forward edges / cross edges : use time.

§ Which of these can exist in an undirected graph?

• Tree edges do exist. They better! That's how we visit new nodes.
• Forward edges: can't happen, because we will always traverse "backwards".

A ----> B
  ----> C

A -> C is a forward edge! If we made the above undirected, then we will have A -> B tree edge and B -> C back-edge.

• Back-edges: can exist in an undirected graph as shown above; B -> C is a back edge.
• Cross-edges: once again, cross edges can only come up from "wrongly directed" edges. But we don't have directions in an undirected graph.

§ Cycle detection

$G$ has a cycle iff $G$'s DFS has a back-edge.

§ Proof: DFS has a back edge => $G$ has a cycle

  tree
A -...-> X
^         |
---back---*

By definition, A -> X is connected using tree edges, and a back edge X -> A. gives us the cycle.

§ Proof: $G$ has a cycle => DFS has a back edge

Say we have a cycle made of k vertices x, y, z, .... assume v[0] is the first vertex in the cycle visited by the DFS. Keep labeling based on how DFS visits then as v[1], v[2], ... v[k]. The we claim the edge v[k] -> v[0] will be a backedge.

• We know that when we're recursing on v[0], we will visit v[1] before we finish v[0].
• Similarly, v[i] will be visited before v[i-1].
• Chaining, we will finish v[k] before we finish v[0].
• In terms of balanced parens, it's like {0 (k; k) 0}.
• So, when we look at the edge v[k] -> v[0], we have not yet finished v[0]. Thus, we get a backedge.

§ Topological sort

Given a DAG, order vertices so that all edges point from lower order to higher order. The algorithm is to run DFS and output the reverse order of finishing time of vertices. Why does this work?

§ Proof that topological sort works

We want to show that for an edge $(u, v)$ that $v$ finishes before $u$, so that $v$ is ordered after $u$. Remember that we sort based on reverse of finishing order.

§ Case 1: u starts before v

We will eventually visit v in the recursion for u because u -> v is an edge. So, we will have the bracketing {u (v; v) u} so we're good: we finish v before we finish u.

§ Case 2: v starts before u

We have the bracketing (v ... {u. If we were to finish u before finishing v, then v is an ancestor of u, and this gives the bracketing (v .. {u .. u} .. v) and thus the edge $(u, v)$ is a back-edge. But this is impossible because the graph cannot have cycles! Thus, we will still have that v finishes beofre u, giving the bracketing (v v) .. {u u}.

• MIT introduction to algorithms: Lecture 14, DFS and topological sorting