GateShala
Playground

DFS Applications (Edge Types, Cycles, Components)

Discovery and finish times, classifying edges, detecting cycles and finding strongly connected components.

Depth-first search does more than visit every vertex. If we record when each vertex is first discovered and when it is finished, the resulting timestamps reveal the structure of the graph.

Discovery and finish times

Keep a global clock. When DFS first reaches a vertex u, set d[u] = ++time and colour u grey ("in progress"). When all its neighbours are done, set f[u] = ++time and colour it black ("finished").

ABCDEFG
The directed graph used in this lesson

Classifying edges

When DFS at u looks along an edge (u, v):

Edge typeColour of v when (u, v) is examinedMeaning
Tree edgewhite (not yet discovered)DFS goes to v through this edge
Back edgegrey (still in progress)v is an ancestor of u: there is a cycle
Forward edgeblack, and d[u] < d[v]v is a descendant of u found another way
Cross edgeblack, and d[u] > d[v]v is in an already-finished branch

In an undirected graph, DFS only produces tree edges and back edges. A directed graph has a cycle if and only if DFS finds a back edge.

Java
Open in playground
import java.util.*;

public class Main {
    static Map<Character, List<Character>> adj = new TreeMap<>();
    static Map<Character, Integer> d = new HashMap<>(), f = new HashMap<>();
    static Map<Character, Character> color = new HashMap<>();   // W, G or B
    static int time = 0;
    static List<String> edges = new ArrayList<>();

    static void dfs(char u) {
        d.put(u, ++time);
        color.put(u, 'G');
        for (char v : adj.get(u)) {
            char c = color.get(v);
            String type = c == 'W' ? "tree" : c == 'G' ? "back" : d.get(u) < d.get(v) ? "forward" : "cross";
            edges.add(u + "->" + v + " " + type);
            if (c == 'W') dfs(v);
        }
        color.put(u, 'B');
        f.put(u, ++time);
    }

    public static void main(String[] args) {
        String[] list = {"AB", "AC", "BC", "BD", "CA", "DE", "EF", "FD", "GF"};
        for (char v = 'A'; v <= 'G'; v++) { adj.put(v, new ArrayList<>()); color.put(v, 'W'); }
        for (String e : list) adj.get(e.charAt(0)).add(e.charAt(1));

        for (char v : adj.keySet()) if (color.get(v) == 'W') dfs(v);

        StringBuilder times = new StringBuilder();
        for (char v : adj.keySet()) times.append(v).append(' ').append(d.get(v)).append('/').append(f.get(v)).append("  ");
        System.out.println("d/f: " + times.toString().trim());
        System.out.println("edges: " + String.join(", ", edges));
        System.out.println("has a cycle: " + edges.stream().anyMatch(s -> s.endsWith("back")));
    }
}
Output
d/f: A 1/12  B 2/11  C 3/4  D 5/10  E 6/9  F 7/8  G 13/14
edges: A->B tree, B->C tree, C->A back, B->D tree, D->E tree, E->F tree, F->D back, A->C forward, G->F cross
has a cycle: true

The edges are printed in the order DFS examines them. A->C comes near the end: DFS reaches C through B first, and only looks at A's second edge after B's whole subtree is finished, so by then C is black and the edge is a forward edge. The parenthesis theorem holds: for any two vertices, their [d, f] intervals are either nested or disjoint. For example B's interval [2, 11] contains C's [3, 4].

Connected components

In an undirected graph, each call of DFS (or BFS) from an unvisited vertex discovers exactly one connected component. Counting the calls counts the components, in O(V + E) time.

Strongly connected components

In a directed graph, a strongly connected component (SCC) is a maximal set of vertices in which every vertex can reach every other. In the graph above the SCCs are {A, B, C}, {D, E, F} and {G}.

Kosaraju's algorithm finds them in O(V + E):

  1. Run DFS on the graph and note the order in which vertices finish.
  2. Reverse every edge (the transpose graph).
  3. Run DFS on the transpose, starting vertices in decreasing finish time. Each tree of this second DFS is one SCC.
Java
Open in playground
import java.util.*;

public class Main {
    static Map<Character, List<Character>> adj = new TreeMap<>(), rev = new TreeMap<>();
    static Set<Character> seen = new HashSet<>();
    static Deque<Character> finished = new ArrayDeque<>();

    static void dfs1(char u) {
        seen.add(u);
        for (char v : adj.get(u)) if (!seen.contains(v)) dfs1(v);
        finished.push(u);                       // stack: latest finish on top
    }

    static void dfs2(char u, List<Character> comp) {
        seen.add(u);
        comp.add(u);
        for (char v : rev.get(u)) if (!seen.contains(v)) dfs2(v, comp);
    }

    public static void main(String[] args) {
        for (char v = 'A'; v <= 'G'; v++) { adj.put(v, new ArrayList<>()); rev.put(v, new ArrayList<>()); }
        for (String e : new String[]{"AB", "AC", "BC", "BD", "CA", "DE", "EF", "FD", "GF"}) {
            adj.get(e.charAt(0)).add(e.charAt(1));
            rev.get(e.charAt(1)).add(e.charAt(0));
        }
        for (char v : adj.keySet()) if (!seen.contains(v)) dfs1(v);

        seen.clear();
        List<List<Character>> sccs = new ArrayList<>();
        while (!finished.isEmpty()) {
            char u = finished.pop();
            if (seen.contains(u)) continue;
            List<Character> comp = new ArrayList<>();
            dfs2(u, comp);
            Collections.sort(comp);
            sccs.add(comp);
        }
        System.out.println(sccs.size() + " SCCs: " + sccs);
    }
}
Output
3 SCCs: [[G], [A, B, C], [D, E, F]]

Shrinking every SCC to a single vertex always leaves a directed acyclic graph (the condensation), which can then be topologically sorted.

GATE-style practice questions

GATE-styleMCQ · one correct answer

During DFS of a directed graph, an edge (u, v) is examined when v is grey (discovered but not finished). What kind of edge is it, and what does it tell you?

Show answer and explanationAnswer: B

A grey vertex is still on the recursion stack, so it is an ancestor of u. The edge u → v closes a path v → ... → u → v, which is a cycle.

GATE-styleMSQ · one or more correct answers

In a DFS of an undirected graph, which kinds of edges can appear? (Select all that apply.)

Show answer and explanationAnswer: A, B

In an undirected graph every edge is explored from both ends. If (u, v) were a forward or cross edge from u's side, DFS would already have explored it from v's side earlier as a tree or back edge. So only tree and back edges occur.

GATE-styleNAT · numerical answer

How many strongly connected components does the directed graph with vertices 1 to 6 and edges 1→2, 2→3, 3→1, 3→4, 4→5, 5→4, 5→6 have?

Show answer and explanationAnswer: 3

{1, 2, 3} form a cycle, {4, 5} form a cycle, and 6 cannot reach anything else, so it is alone. The SCCs are {1, 2, 3}, {4, 5} and {6}.

GATE-styleNAT · numerical answer

An undirected graph has 15 vertices and 10 edges and contains no cycle. How many connected components does it have?

Show answer and explanationAnswer: 5

A forest (an acyclic undirected graph) with V vertices and E edges has exactly V − E components, because each tree with k vertices has k − 1 edges. So 15 − 10 = 5.