Link Search Menu Expand Document

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

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.)

Undirected Graph with 7 Nodes

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|)
Explanation

Consider the case where the graph is dense (|E| ≈ |V|2) and connected (every node is connected to every other node). From the start vertex, BFS will eventually need to consider every edge in the graph. In this sense, we have O(|E|).

Note that this answer depends on the implementation details, especially the visited data structure. Some other sources might cite O(|E|) as incorrect if they need to initialize a visited data structure with entries for every vertex—even in the case that the start vertex is completely disconnected from the rest of the graph. Furthermore, there are some variants of BFS where the algorithm continues from the next unvisited node when the perimeter is exhausted.

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.

Taj Mahal Flood Fill

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
Explanation

In an undirected graph, the shortest path from s to t will be the same as the shortest path from t to s, so BFS in either direction works. However, we can’t run a BFS from any node and expect to get the correct shortest path from s to t. For example, consider a triangular graph with 3 vertices: r, s, and t. BFS from r will not store the shortest path from s to t in its edgeTo map.

In general, DFS is not guaranteed to return the unweighted shortest path.

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.)

Undirected Graph with 7 Nodes

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.

Graph with 3 Components

Question 1

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

Question 2

Starry night sky

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.

Facial detection system

Explanation

We might also call into question how facial recognition systems are used in policing systems, and how skin tone bias may lead to different answers on behalf of the police that use the system as well as the developers that attempt to respond to these questions around bias. We might further critique the desirability of developing better facial recognition systems if they will be used to disproportionately harm minoritized communities and draw resources away from more restorative solutions to social problems.