# Graph Traversals

## Table of contents

- s-t connectivity
- Breadth-first search
- Why DFS and BFS
- Graph problems
- Graph traversal
- BFS vs DFS
- 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*|)

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

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

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

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