Graph Traversals

Table of contents

1. s-t connectivity
2. Breadth-first search
3. Why DFS and BFS
4. Graph problems
5. Graph traversal
6. BFS vs DFS
7. Connected components

s-t connectivity

Breadth-first search

Why DFS and BFS

Graph problems

Graph traversal

The breadth-first search (BFS) algorithm traverses all of the vertices in a graph from a start vertex.

bfs(Graph graph, Vertex start) {
    Queue<Vertex> perimeter = new Queue<>();
    Set<Vertex> visited = new Set<>();

    perimeter.add(start);
    visited.add(start);

    while (!perimeter.isEmpty()) {
        Vertex from = perimeter.remove();
        for (Edge edge : graph.neighbors(from)) {
            Vertex to = edge.to();
            if (!visited.contains(to)) {
                perimeter.add(to);
                visited.add(to);
            }
        }
    }
}

Question 1

Reorder the elements such that it represents the order in which BFS removes each node from the perimeter starting from 0. Visit neighbors in increasing order. (For example, visit 1 before 4.)

Question 2

Given a simple undirected graph, which of the following runtime bounds correctly describes the runtime of BFS in terms of the number of vertices |V| and the number of edges |E|?

• O(|V|)
• O(|E|)
• O(|V| + |E|)

Question 3

In the following images (Sedgewick and Wayne 2020), the original image on the left has its sky flood-filled with gray on the right.

Describe how to implement flood fill, a photo editing feature that replaces adjacent pixels that are similar in color value. Define a graph abstraction for this problem by describing its nodes and edges. If your implementation needs to modify the BFS or DFS traversal, describe the necessary changes.

BFS vs DFS

The recursive depth-first search (DFS) algorithm traverses all of the vertices in a graph from a start vertex.

Set<Vertex> visited = new Set<>();

dfs(Graph graph, Vertex start) {
    visited.add(start);
    for (Edge edge : graph.neighbors(from)) {
        Vertex to = edge.to();
        if (!visited.contains(to)) {
            dfs(graph, to);
        }
    }
}

Question 1

Which of the following algorithms could be used to find the shortest path in an unweighted, undirected graph from s to t?

• Run BFS from s
• Run BFS from t
• Run BFS from any node
• Run DFS from s
• Run DFS from t
• Run DFS from any node

Question 2

Reorder the elements such that it represents the order in which recursive DFS visits each node starting from 0. Visit neighbors in increasing order. (For example, visit 1 before 4.)

Question 3

Say we want to implement an iterative DFS by taking the bfs implementation and swapping out the Queue for a Stack. Assume that we also modified the Graph.neighbors method to iterate over edges in decreasing order so that neighbors are correctly removed from the stack in increasing order.

dfs(Graph graph, Vertex start) {
    Stack<Vertex> perimeter = new Stack<>();
    Set<Vertex> visited = new Set<>();

    perimeter.push(start);
    visited.add(start);

    while (!perimeter.isEmpty()) {
        Vertex from = perimeter.pop();
        for (Edge edge : graph.neighbors(from)) {
            Vertex to = edge.to();
            if (!visited.contains(to)) {
                perimeter.push(to);
                visited.add(to);
            }
        }
    }
}

However, when we run this (broken) iterative DFS algorithm on the above graph, the result is not actually a valid DFS traversal. Explain what part of the code might be causing the problem.

Connected components

A connected component (aka component) of an undirected graph is a set of nodes that are connected to each other but disconnected from other nodes in the graph. The following graph contains 3 components.

Question 1

Describe an algorithm for finding all connected components in an undirected graph.

Question 2

How might we use connected components to identify stars in the night sky? Define a graph abstraction for this problem by describing its nodes and edges.

Question 3

Give an affordance analysis for connected components in the context of a facial recognition system (Borah et al. 2014). The system takes an input image, detects pixels corresponding to skin tones, extracts skin tone pixels, and then uses connected components to compute the bounding box for the face.