Graphs: representation, BFS, DFS and topological sort

In trees every node had a single parent. A graph removes this restriction: there can be a connection between any two vertices, there can be cycles, there can be no connection at all. A road map, a social network, course prerequisites and internet links are all graphs. Next week we will run shortest-path algorithms on them; this week we lay the foundation: how do we store a graph and how do we traverse it.

The questions that will come from this week in the exam:

1. Representation: “Write the adjacency list/matrix of this graph”, “how much memory?”
2. Traversal order: “Do BFS/DFS from 0 and write the visit order.” The rule is usually “visit neighbors in ascending order”.
3. Topological sort: a valid course order in a prerequisite graph.
4. Writing a method: BFS, DFS or counting components.

Terms

In an undirected graph each edge contributes to the degree of two vertices, so the sum of degrees = 2E. A graph with V vertices has at most $V(V-1)/2$ edges (for directed, $V(V-1)$). If E is near this limit the graph is dense, and if it is on the order of V it is sparse.

The example graph G

All the traversal examples on this page use this graph:

  1 --- 3 --- 0
  |     |     |
  4 --- 6 --- 5 --- 2 --- 7

Edges: 0-3, 0-5, 1-3, 1-4, 2-5, 2-7, 3-6, 4-6, 5-6. In total 9 edges, the sum of degrees is 18.

Representation 1: the adjacency matrix

A V×V boolean or int array: if a[u][v] = 1 there is an edge. In an undirected graph the matrix is symmetric. A small example, edges 0-1, 0-2, 1-2, 2-3:

     0  1  2  3
 0 [ 0, 1, 1, 0 ]
 1 [ 1, 0, 1, 0 ]
 2 [ 1, 1, 0, 1 ]
 3 [ 0, 0, 1, 0 ]

In a weighted graph the weight is written instead of 1, and infinity (or 0) is put if there is no edge. The advantage: the question “are u and v connected?” is $O(1)$. The disadvantage: $V^2$ memory regardless of the number of edges. For a road network with 1 million vertices, there would be $10^{12}$ cells.

Representation 2: the adjacency list

For each vertex, a list of its neighbors. In Java the most practical form is List<List<Integer>>:

int n = 8;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[][] edges = {{0,3},{0,5},{3,1},{3,6},{5,6},{5,2},{1,4},{6,4},{2,7}};
for (int[] e : edges) {
    adj.get(e[0]).add(e[1]);   // undirected: add in both directions
    adj.get(e[1]).add(e[0]);
}
for (List<Integer> l : adj) Collections.sort(l);
System.out.println(adj);

[[3, 5], [3, 4], [5, 7], [0, 1, 6], [1, 6], [0, 2, 6], [3, 4, 5], [2]]

The total length of the lists is 2E for undirected and E for directed. Memory is $O(V + E)$.

Since real graphs are almost always sparse, the default choice is the list.

Breadth-first search (BFS)

BFS spreads from the start level by level: first those 1 edge away, then 2, then 3. The tool is a queue.

static void bfs(List<List<Integer>> adj, int s) {
    int[] dist = new int[adj.size()];
    Arrays.fill(dist, -1);              // -1 = not seen
    Deque<Integer> q = new ArrayDeque<>();
    dist[s] = 0;
    q.add(s);
    while (!q.isEmpty()) {
        int v = q.poll();
        System.out.print(v + " ");
        for (int w : adj.get(v))
            if (dist[w] == -1) {        // seen for the first time
                dist[w] = dist[v] + 1;
                q.add(w);
            }
    }
}

The trace from 0 on G:

dequeued  added    queue
0         3, 5     [3, 5]
3         1, 6     [5, 1, 6]
5         2        [1, 6, 2]
1         4        [6, 2, 4]
6         -        [2, 4]
2         7        [4, 7]
4         -        [7]
7         -        []
order: 0 3 5 1 6 2 4 7
dist: 0:0 1:2 2:2 3:1 4:3 5:1 6:2 7:3

The superpower of BFS: in an unweighted graph the dist array is exactly the number of edges of the shortest path. A vertex enters the queue for the first time with its shortest distance, because the queue processes distances in order. If you keep a parent array you can also reconstruct the path itself.

PITFALL · when do you mark? Mark the vertex as seen when adding it to the queue. If you mark when removing, the same vertex enters the queue more than once: 6 would be added from both 3 and 5. The order and the complexity break.

Depth-first search (DFS)

DFS goes as far as it can along one path, and when it hits a dead end it goes back (backtracking). Its recursive form is very similar to the preorder traversal of a tree; the only difference is the visited array, because a graph has cycles.

static void dfs(List<List<Integer>> adj, int v, boolean[] visited) {
    visited[v] = true;
    System.out.print(v + " ");
    for (int w : adj.get(v))
        if (!visited[w]) dfs(adj, w, visited);
}

From 0 on G:

dfs(0) -> 3
  dfs(3) -> 0 seen, 1
    dfs(1) -> 3 seen, 4
      dfs(4) -> 1 seen, 6
        dfs(6) -> 3, 4 seen, 5
          dfs(5) -> 0 seen, 2
            dfs(2) -> 5 seen, 7
              dfs(7) -> go back
order: 0 3 1 4 6 5 2 7

DFS with a stack

Instead of recursion, an explicit stack can be used: pop a vertex, skip it if it is visited, otherwise visit it and push its unvisited neighbors. Here the order changes:

push neighbors in ASCENDING order:  0 5 6 4 1 3 2 7
push neighbors in DESCENDING order: 0 3 1 4 6 5 2 7

Since the stack works on last-in first-out logic, if you push in ascending order the largest neighbor comes out first. If you want the same order as recursive DFS, push the neighbors in reverse order. If the exam says “using a stack”, be sure to account for this difference.

BFS and DFS compared

Connected components

If the graph is not connected, a single BFS/DFS cannot reach every vertex. The solution: go through the vertices in order, and start a new traversal from every unvisited one. Each start means one component.

Vertices 0..8, edges 0-1, 1-2, 3-4, 5-6, 6-7, 5-7:

0 - 1 - 2     3 - 4     5 - 6     8
                         \ /
                          7
component labels: [0,0,0,1,1,2,2,2,3]
number of components: 4

The vertex 8, which has no edges, is also a component on its own. The whole code is in the question bank.

Topological sort

An ordering of vertices in a directed graph in which, for every edge u→v, u comes before v. The classic example is course prerequisites: if SEN2211 → SEN2212, then 2211 is taken first. It is possible only in a DAG; if there is a cycle (A is a prerequisite of B and B of A) there is no valid order.

An example DAG, edges 4→2, 4→0, 6→0, 6→5, 2→1, 0→1, 0→3, 5→3:

4 ---> 2 ---> 1
 \            ^
  v           |
   0 ---------+
  ^ \
 /   v
6     3
 \    ^
  v   |
   5 -+

Kahn’s algorithm (with in-degrees)

1. Compute the in-degree of every vertex.
2. Put the vertices with degree 0 in the queue.
3. Dequeue, write to the output. Decrease the degree of its neighbors by 1; add the one that drops to 0 to the queue.

in-degree: 0:2 1:2 2:1 3:2 4:0 5:1 6:0
queue [4, 6]
dequeue 4 -> 2 freed        [6, 2]
dequeue 6 -> 0, 5 freed     [2, 0, 5]
dequeue 2 -> (1 is still 1) [0, 5]
dequeue 0 -> 1 freed        [5, 1]
dequeue 5 -> 3 freed        [1, 3]
dequeue 1, dequeue 3
order: 4 6 2 0 5 1 3

If you use a min-heap instead of a queue and pick the smallest label each time, the order is 4 2 6 0 1 5 3. Both are valid: a topological order is usually not unique, and the rule in the question decides.

Cycle detection comes for free: if there are fewer than V vertices in the output when Kahn finishes, the graph has a cycle, because the degrees of the vertices in the cycle never drop to 0. In the graph with edges 0→1, 1→2, 2→0, 2→3, no vertex has in-degree 0; the output has 0 vertices.

Topological order with DFS

In DFS a vertex finishes after all its descendants have finished. So for an edge u→v, v finishes before u. If you reverse the finishing order, you get the topological order.

dfs(0): 1 finishes, 3 finishes, 0 finishes
dfs(2): 2 finishes        dfs(4): 4 finishes
dfs(5): 5 finishes        dfs(6): 6 finishes
finish:   1 3 0 2 4 5 6
reversed: 6 5 4 2 0 3 1

Check: 6→0 (6 first), 4→2, 2→1, 0→3, 5→3: all in the right direction. Both algorithms are $O(V + E)$.

Common mistakes

static int countComponents(List<List<Integer>> adj) {
    int n = adj.size(), count = 0;
    boolean[] visited = new boolean[n];
    for (int v = 0; v < n; v++) {
        if (!visited[v]) {
            count++;
            dfs(adj, v, visited);
        }
    }
    return count;
}

static void dfs(List<List<Integer>> adj, int v, boolean[] visited) {
    visited[v] = true;
    for (int w : adj.get(v))
        if (!visited[w]) dfs(adj, w, visited);
}