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
- Tree edges : visit a new vertex via that edge. Parent pointers track tree edges.
- forward edges : goes from node
n
to descendant of node n
. - backward edges : goes from a node
n
to an ancestor of node n
. - 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}
.