DFS edge types, topological sort and SCC

Why it exists

A depth-first search of a directed graph does more than visit the vertices: the kind of every edge it meets carries information. A back edge means a cycle; no back edge means the graph is a DAG (directed acyclic graph), and then the order in which the vertices finish gives a topological order, the way to schedule tasks that depend on each other. Running the search twice, on the graph and on its reversal, splits any graph into its strongly connected components. These three results (cycle detection, topological sort, SCC) are standard GATE material.

Prerequisites

You need depth-first search with colours and discovery and finish times (BFS and DFS).

Precise definitions

Directed graph. Edges $u \to v$ have a direction. Adjacency lists hold only the edges that leave a vertex.

Edge types of a depth-first forest, for an edge $u \to v$:

• Tree edge: the search reaches $v$ for the first time through this edge ($v$ is white when the edge is examined).
• Back edge: $v$ is an ancestor of $u$ (or $u$ itself, a self-loop): $v$ is gray.
• Forward edge: $v$ is a descendant of $u$ but the edge is not a tree edge: $v$ is already black and was discovered after $u$.
• Cross edge: every other edge: $v$ is black and was discovered before $u$, in another branch or another tree.

Directed acyclic graph (DAG). A directed graph with no directed cycle.

Topological order. A list of all vertices in which every edge $u \to v$ has $u$ before $v$. It exists exactly for DAGs.

Strongly connected. Two vertices $u$ and $v$ are in the same strongly connected component (SCC) if there is a path from $u$ to $v$ and a path from $v$ to $u$. The components partition the vertices; contracting each to a point gives the component graph, which is always a DAG.

How it works

Classifying edges

The animation runs the real code on a directed graph with $8$ vertices and $11$ edges. The kind of each edge is chosen by the same four lines that the page shows: white means tree, gray means back, black means forward if $d[u] < d[v]$ and cross otherwise.

The program prints every edge with its kind and then, further down, the times and the strongly connected components of this graph.

#include <stdio.h>
 
#define N 8
 
static int deg[N], nbr[N][N];                /* edges that leave each vertex, in increasing order */
static int tdeg[N], tnbr[N][N];              /* the reversed graph */
 
enum { WHITE, GRAY, BLACK };
static int color[N], disc[N], fin[N], timer, finish_order[N], nfin;
 
static void dfs_visit(int u, int print) {
    color[u] = GRAY;
    disc[u] = ++timer;
    for (int k = 0; k < deg[u]; k++) {
        int v = nbr[u][k];
        const char *kind;
        if (color[v] == WHITE) kind = "tree";
        else if (color[v] == GRAY) kind = "back";
        else if (disc[u] < disc[v]) kind = "forward";
        else kind = "cross";
        if (print) printf("edge %d -> %d %s\n", u, v, kind);
        if (color[v] == WHITE) dfs_visit(v, print);
    }
    color[u] = BLACK;
    fin[u] = ++timer;
    finish_order[nfin++] = u;
}
 
static int comp[N];
static void collect(int u, int c) {              /* a depth-first search in the reversed graph */
    comp[u] = c;
    for (int k = 0; k < tdeg[u]; k++) if (comp[tnbr[u][k]] < 0) collect(tnbr[u][k], c);
}
 
int main(void) {
    int E[11][2] = {{0, 1}, {0, 3}, {1, 2}, {2, 0}, {2, 3}, {3, 4}, {4, 5}, {5, 3}, {6, 5}, {6, 7}, {7, 6}};
    for (int i = 0; i < 11; i++) { nbr[E[i][0]][deg[E[i][0]]++] = E[i][1]; tnbr[E[i][1]][tdeg[E[i][1]]++] = E[i][0]; }
    for (int v = 0; v < N; v++) if (color[v] == WHITE) dfs_visit(v, 1);
    printf("times (disc/fin):");
    for (int v = 0; v < N; v++) printf(" %d:%d/%d", v, disc[v], fin[v]);
    printf("\nfinish order:");
    for (int i = 0; i < nfin; i++) printf(" %d", finish_order[i]);
    printf("\n");
    for (int v = 0; v < N; v++) comp[v] = -1;
    int count = 0;
    for (int i = N - 1; i >= 0; i--) {                       /* decreasing finish time */
        int r = finish_order[i];
        if (comp[r] < 0) {
            collect(r, count);
            printf("component %d (root %d):", count, r);
            for (int v = 0; v < N; v++) if (comp[v] == count) printf(" %d", v);
            printf("\n");
            count++;
        }
    }
    printf("%d strongly connected components\n", count);
    return 0;
}

edge 0 -> 1 tree
edge 1 -> 2 tree
edge 2 -> 0 back
edge 2 -> 3 tree
edge 3 -> 4 tree
edge 4 -> 5 tree
edge 5 -> 3 back
edge 0 -> 3 forward
edge 6 -> 5 cross
edge 6 -> 7 tree
edge 7 -> 6 back
times (disc/fin): 0:1/12 1:2/11 2:3/10 3:4/9 4:5/8 5:6/7 6:13/16 7:14/15
finish order: 5 4 3 2 1 0 7 6
component 0 (root 6): 6 7
component 1 (root 0): 0 1 2
component 2 (root 3): 3 4 5
3 strongly connected components

The same facts in terms of the time stamps (all four kinds can be recognised afterwards from the intervals): for $u \to v$

Consequences.

1. In a depth-first search of an undirected graph every edge is a tree edge or a back edge (forward edges are the same edges seen from the other end); there are no cross edges.
2. A directed graph has a cycle if and only if the search finds a back edge. (A back edge $u \to v$ closes the cycle $v \leadsto u \to v$ along the tree path; conversely, a cycle has a first vertex discovered, and the vertex before it on the cycle becomes its descendant by the white-path theorem and gives a back edge.)
3. In a DAG, for every edge $u \to v$ we have $f[u] > f[v]$.

Topological sort

By depth-first search. Run DFS, and write the vertices in decreasing finish time (put each vertex at the front of a list when it finishes). By fact 3 every edge goes from a vertex that finishes later to one that finishes earlier, so it points forward in the list. Time $\Theta(V + E)$.

Kahn's algorithm. Repeatedly remove a vertex with in-degree $0$ and delete its outgoing edges (decreasing the in-degrees of its targets), appending the removed vertices in order. If the graph has a cycle the algorithm gets stuck with vertices left over (all remaining in-degrees positive): this is also a cycle test. Time $\Theta(V + E)$.

A DAG usually has many topological orders. The program below computes the order from DFS, Kahn's order (always taking the smallest available vertex), and counts all valid orders by trying every permutation of the $8$ vertices.

#include <stdio.h>
 
#define N 8
 
static int deg[N], nbr[N][N], indeg[N];
 
enum { WHITE, GRAY, BLACK };
static int color[N], order[N], pos;
 
static void dfs_visit(int u) {
    color[u] = GRAY;
    for (int k = 0; k < deg[u]; k++) if (color[nbr[u][k]] == WHITE) dfs_visit(nbr[u][k]);
    color[u] = BLACK;
    order[--pos] = u;                              /* a vertex is put in front of everything finished before it */
}
 
static int valid(const int p[]) {                  /* every edge goes from an earlier to a later vertex */
    int at[N];
    for (int i = 0; i < N; i++) at[p[i]] = i;
    for (int u = 0; u < N; u++) for (int k = 0; k < deg[u]; k++) if (at[u] > at[nbr[u][k]]) return 0;
    return 1;
}
 
static long count_orders(int p[], int used, int k) {   /* tries every permutation */
    if (k == N) return valid(p);
    long total = 0;
    for (int v = 0; v < N; v++) if (!(used >> v & 1)) { p[k] = v; total += count_orders(p, used | 1 << v, k + 1); }
    return total;
}
 
int main(void) {
    int E[9][2] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 5}, {3, 4}, {5, 4}, {6, 2}, {6, 7}};
    for (int i = 0; i < 9; i++) { nbr[E[i][0]][deg[E[i][0]]++] = E[i][1]; indeg[E[i][1]]++; }
    pos = N;
    for (int v = 0; v < N; v++) if (color[v] == WHITE) dfs_visit(v);
    printf("DFS order (decreasing finish time):");
    for (int i = 0; i < N; i++) printf(" %d", order[i]);
    printf("  valid: %s\n", valid(order) ? "yes" : "no");
    int kahn[N], done = 0, d[N];
    for (int v = 0; v < N; v++) d[v] = indeg[v];
    while (done < N) {                             /* Kahn: repeatedly remove the smallest vertex of in-degree 0 */
        int u = -1;
        for (int v = 0; v < N; v++) {
            int taken = 0;
            for (int i = 0; i < done; i++) if (kahn[i] == v) taken = 1;
            if (!taken && d[v] == 0) { u = v; break; }
        }
        kahn[done++] = u;
        for (int k = 0; k < deg[u]; k++) d[nbr[u][k]]--;
    }
    printf("Kahn order (smallest in-degree-0 vertex first):");
    for (int i = 0; i < N; i++) printf(" %d", kahn[i]);
    printf("  valid: %s\n", valid(kahn) ? "yes" : "no");
    int p[N];
    printf("number of different topological orders: %ld\n", count_orders(p, 0, 0));
    return 0;
}

DFS order (decreasing finish time): 6 7 0 2 5 1 3 4  valid: yes
Kahn order (smallest in-degree-0 vertex first): 0 1 6 2 3 5 4 7  valid: yes
number of different topological orders: 75

When is the order unique? Exactly when the DAG has a path through all vertices, that is, when consecutive vertices in the order are joined by edges (checked on 300 random DAGs). Otherwise there are at least two orders.

Strongly connected components (Kosaraju)

1. Run DFS on $G$ and record the finish times.
2. Build the reversed graph $G^{T}$ (all edges turned round). It has the same strongly connected components.
3. Run DFS on $G^{T}$, starting new trees from the vertices in decreasing finish time (of step 1). Each tree of this second search is one strongly connected component.

Why: in $G$, the component that contains the vertex with the largest finish time is a source of the component graph (nothing enters it from another component); in $G^T$ it is a sink, so the search started there cannot leave it. Remove it and repeat. The components come out in a topological order of the component graph. Time $\Theta(V + E)$. (Tarjan's algorithm finds the components in one search using low-link values.)

The graph has three components: $\{6, 7\}$ (a $2$-cycle, with an edge $6 \to 5$ leaving it), $\{0, 1, 2\}$ (a $3$-cycle, with edges to $3$) and $\{3, 4, 5\}$ (a $3$-cycle). The component graph $\{6,7\} \to \{3,4,5\}$ and $\{0,1,2\} \to \{3,4,5\}$ is a DAG, and the components were found in an order consistent with it ($\{6, 7\}$, then $\{0, 1, 2\}$, then $\{3, 4, 5\}$).

Worked examples

Cheat box

Traps and GATE patterns

Connections

All of this is DFS (BFS and DFS) with the colour rule. The reachability relation computed here for strong connectivity is the transitive closure that Floyd-Warshall computes for all pairs; the graphs are represented as in graph representations.

PYQs

Let G be a weighted directed acyclic graph with m
edges and n vertices. Given G and a source vertex s
in G, which one of the following options gives the
worst case time complexity of the fastest algorithm
to find the lengths of shortest paths from s to all
vertices that are reachable from s in G?

Consider the following pseudocode for depth-first
search (DFS) algorithm which takes a directed
graph G(V,E) as input, where d[v] and f[v] are the
discovery time and finishing time, respectively, of
the vertex v ∈V.

DFS(G) :
unmark all v ∈ V
t ← 0
for each v ∈ V
if v is unmarked
t ← Explore
(G, v, t )
end if
end for
Explore ( G, v, t ):
mark v
t ← t + 1
d[v] ← t
for each (v, w) ∈ E
if w is unmarked
t ← Explore (G, w, t)
end if
end for
t ← t + 1
f[v] ← t
return t
Suppose that the input directed graph G(V,E) is a
directed acyclic graph (DAG). For an edge
(u,v)∈E, which of the following options will
NEVER be correct?

Which of the following statements regarding
Breadth First Search (BFS) and Depth First Search
(DFS) on an undirected simple graph G is/are
TRUE?

Let G be a directed graph and T a depth first search
(DFS) spanning tree in G that is rooted at a vertex

Match Let G be a simple undirected graph. Let TD be
a depth first search tree of G. Let TB be a breadth
first search tree of G. Consider the following
statements.
(I) No edge of G is a cross edge with respect to TD.
(A cross edge in G is between two nodes neither of
which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v
is at depth j in TB, then |i - j| = 1.
Which of the statements above must necessarily be
true?

A depth-first search is performed on a directed
acyclic graph. Let d[u] denote the time at which
vertex u is visited for the first time and f[u] the time
at which the DFS call to the vertex u terminates.
Which of the following statements is always TRUE
for all edges (u, v) in the graph ?

Consider the DAG with V = {1,2,3,4,5,6}, shown
below

Which of the following is NOT a topological
ordering?

Consider the depth-first-search of an undirected
graph with 3 vertices P, Q, and R. Let discovery
time d(u) represent the time instant when the
vertex u is first visited, and finish time f(u)
represent the time instant when the vertex u is last
visited. Given that
d(P)=5 units f(P)=12 units
d(Q)=6 units f(Q)=10 units
d(R)=14 unitf(R)=18 units
Which one of the following statements is TRUE
about the graph?

Let T be a depth first search tree in a undirected
graph G. Vertices u and v are leaves of this tree T.
The degrees of both u and v in G are at least 2.
Which one of the following statements is true?

An articulation point in a connected graph is a
vertex such that removing the vertex and its
incident edges disconnects the graph into two or
more connected components. Let T be a DFS three

Self-check

Revision card

References