Lecture 25:

DFS & BFS

CS 136: Spring 2024

Katie Keith

Record on Zoom

• Please fill out the final project partner preference Google form.
• Due: Today at 10pm ET.
• 1-page project proposal due next Monday (May 5)
• Lab 7 due today or tomorrow
• Lab 8: Released. Final lab!
• Due: Weds May 7 (Weds lab groups), Thurs, May 8 (Thurs lab groups)
• Reminder, late days only for labs (not projects)

📣 Announcements

📚Readings

• Sedgewick and Wayne. Algorithms. Section 4.1.

Review: Graphs

A graph is a set of vertices and a collection of edges, each of which connect a pair of vertices.

Vertex

Edge

Undirected edge (no arrow on either side)

Review: Undirected Graph ADT

Review: Internet circa 1972

Important graph operations:

• Traversal between vertices
• Finding shortest paths between vertices

Bolt Beranek and Newman (BBN), was a research and development firm.

Now: Raytheon

Review: Reachability

A vertex v in graph G is reachable from vertex u in G if there is a path from u to v.

Review: Adjacency List Representation

An adjacency list representation of an undirected graph consists of an array where indices are vertices and each array index contains a reference to a linked list of adjacent vertices.

Review: Adjacency Matrix Representation

An adjacency matrix representation of an undirected graph consists of a 2-dimensional array of size VxV where V is the number of vertices in the graph.

A 1 indicates an edge exists (here between vertex 5 and 2)

A 0 indicates an edge does not exists (here between vertex 1 and 5)

Figure source

Vertices

Trade-offs: Adjacency lists versus matrices

Let V be the number of vertices in our graph and let E be the number of edges.

In practice: We typically use adjacency lists

• Depth first search (DFS)
• Breadth first search (BFS)

🎯 Today’s Learning Objectives

Breadth First Search (BFS)

Breadth First Search (BFS) is an algorithm for searching for a path between a pair of vertices in a graph.

The algorithm starts at an initial vertex and explores all vertices at the present depth prior to moving on to vertices at the next depth.

GIF credit: Sebastian De Lima

Note: In a disconnected graph, it’s possible that a path does not exist

Depth First Search (DFS)

Depth-first search (DFS) is an algorithm for searching for a path between a pair of vertices in a graph.

The algorithm starts at an initial vertex and explores as far as possible along each path before backtracking.

​

GIF credit: Sebastian De Lima

Graph DFS & BFS Application: Solving Mazes

Initial vertex (start of maze)

Target vertex (goal/end of maze)

Vertex = One pixel

Edge = True if the pixels are connected

GIF credit: Akira Kunishige

​

Shaded pixel = �“marked” vertex, a vertex our algorithm has visited,

Solving mazes

GIF credit: Akira Kunishige

​

Solving mazes

GIF credit: Akira Kunishige

​

Solving mazes

GIF credit: Akira Kunishige

​

Breadth First Search (BFS) pseudocode

• Maintain a queue of all vertices that have been marked but whose adjacency lists have not been checked.
• We put the source vertex on the queue, then perform the following steps until the queue is empty:
• Remove the next vertex v from the queue.
• Put onto the queue all unmarked vertices that are adjacent to v and mark them.

BFS Example

We’ll represent graph G with an adjacency list

BFS code snippet

//G is a graph

int INF = Integer.MAX_VALUE;

private boolean[] marked = new boolean[G.V()];

private int[] distTo = new int[G.V()];

Queue<Integer> q = new Queue<Integer>();

​

// s is the source vertex

private void bfs(Graph G, int s) {

for (int v = 0; v < G.V(); v++){

distTo[v] = INF;}

distTo[s] = 0;

marked[s] = true;

q.enqueue(s);

​

while (!q.isEmpty()) {

int v = q.dequeue();

for (int w : G.adj(v)) {

if (!marked[w]) {

distTo[w] = distTo[v] + 1;

marked[w] = true;

q.enqueue(w);

}}}}

​

BFS code snippet

//G is a graph

int INF = Integer.MAX_VALUE;

private boolean[] marked = new boolean[G.V()];

private int[] distTo = new int[G.V()];

Queue<Integer> q = new Queue<Integer>();

​

// s is the source vertex

private void bfs(Graph G, int s) {

for (int v = 0; v < G.V(); v++){

distTo[v] = INF;}

distTo[s] = 0;

marked[s] = true;

q.enqueue(s);

​

while (!q.isEmpty()) {

int v = q.dequeue();

for (int w : G.adj(v)) {

if (!marked[w]) {

distTo[w] = distTo[v] + 1;

marked[w] = true;

q.enqueue(w);

}}}}

​

BFS code snippet

//G is a graph

int INF = Integer.MAX_VALUE;

private boolean[] marked = new boolean[G.V()];

private int[] distTo = new int[G.V()];

Queue<Integer> q = new Queue<Integer>();

​

// s is the source vertex

private void bfs(Graph G, int s) {

for (int v = 0; v < G.V(); v++){

distTo[v] = INF;}

distTo[s] = 0;

marked[s] = true;

q.enqueue(s);

​

while (!q.isEmpty()) {

int v = q.dequeue();

for (int w : G.adj(v)) {

if (!marked[w]) {

distTo[w] = distTo[v] + 1;

marked[w] = true;

q.enqueue(w);

}}}}

​

BFS and shortest paths

distTo = {0, 1, 2, 3, 4, 3, 2, 1, 2}

Proposition. For any vertex v that is reachable from a source vertex s, BFS computes a shortest path from s to v (no path from s to v has fewer edges.)

​

Analysis. BFS takes time proportional to V+E in the worst case.

s

Example:

Shortest path from the source (vertex 0) to each of the other vertices in the graph.

Solving mazes

GIF credit: Akira Kunishige

​

Depth First Search (DFS) pseudocode

To visit a vertex v:

• Mark v as having been visited.
• Visit (recursively) all the vertices that are adjacent to v and that have not yet been marked.

DFS code snippet

private boolean[] marked = new boolean[G.V()];

​

// Initially, call with source vertex, dfs(G, s)

// If marked[t] == true, there exists a path from s to t

private void dfs(Graph G, int v) {

marked[v] = true;

for (int w : G.adj(v)) {

if (!marked[w]) {

dfs(G, w);

}

}

}

​

Hint: Recursive call stacks here!

0

1

7

8

6

2

3

5

4

Worksheet: Trace DFS algorithm for the graph below

💡Think-pair-share

• Depth first search (DFS)
• Breadth first search (BFS)

✅

✅

🎯 Today’s Learning Objectives