Colors

  • White: unvisited
  • Gray: encountered
  • Black: explored

Attributes

  • pi[v]: the vertex from which v is encountered
  • s[v]: start time, when the vertex is first encountered
  • f[v]: finishing time, when all the vertex’s neighbors have been visited
def dfs_visit(G, u):
    G.color[u] = gray
    G.time += 1
    G.s[u] = time
    for v in G.neighbor(u):
        if G.color[v] == white:
            G.pi[v] = u
            dfs_visit(G, v)
    G.color[u] = black
    G.time += 1
    G.f[u] = time

def dfs(G):
    for v in G.V:
        G.color[v] = white
        G.f[v] = INF
        G.s[v] = INF
        G.pi[v] = None
    G.time = 0
    for v in G.V:
        if G.color[v] == white:
            dfs_visit(G, v)

Runtime

(Assuming using adjancency list)

  • Visit each vertex once O(|V|)
  • Visit the neighbor of each vertex. Each edge is checked once O(|E|)

Total: O(|V| + |E|)

Cycle detection

Denote I[v] = [s[v], f[v]]. For u, v ∈ V, either I[v] ⊆ I[u] or I[v] ∩ I[u] = None.

I[v] ⊆ I[u] IFF u is an ancestor of v in the DFS forest.

  • Tree edge an edge in the DFS-forest
  • Back edge a non-tree edge pointing from a vertex to its ancestor
  • Forward edge a non-tree edge pointing from a vertex to its descendant
  • Cross edge all other edges

A directed graph contains a cycle IFF DFS yields a back edge

Undirected graph

Every edge is either a tree edge or a back edge.

Cannot have a forward edge as this edge should be already marked as back edge. See here.

Topological sort

Place the vertices in an order such that all edges are pointing to the right side.

  1. Perform DFS
  2. Order vertices in order of decreasing finishing times f[v]

Strongly connected components

Subgraphs with strong connectivity (any pair of vertices can reach each other)

  1. Perform DFS on G
  2. Order vertices in the reverse order of f[v]
  3. Computer G^rev
  4. Perform DFS on G^rev, visiting vertices using order from step 2.
  5. Each tree in DFS forest is SCC.