December 6, 2024 1

BREADTH FIRST SEARCH

EECS 2101

Last updated: November 28, 2024

 2

Graph Traversal (14.3)

• Application example
• Given a graph representation and a vertex s in the graph, find all paths
from s to the other vertices.
• Two common graph traversal algorithms:
• Breadth-First Search (BFS)
• Idea is similar to level-order traversal for trees.
• Implementation uses a queue.
• Gives shortest path from a vertex to another.
• Depth-First Search (DFS)
• Idea is similar to preorder traversal for trees (visit a node then visit its children
recursively).
• Implementation uses a stack (implicitly via recursion).
 3

Level-Order Traversal for Trees

Output: A B F J C D E G H K L M N P Q
 4

Level-Order Traversal for Trees: Algorithm

 5

BFS and Shortest Path Problem

• Given any source vertex s, BFS visits the other vertices at increasing
distances away from s. In doing so, BFS discovers shortest paths from s
to the other vertices.
• What do we mean by “distance”? The number of edges on a path from s
(unweighted graph).
Example
0
Consider s = vertex 1.
8
2
Nodes at distance 1?
1 2 s 9 1 2, 3, 7, 9
1
1
Nodes at distance 2?
3 7 8, 6, 5, 4
1
6 2
4 Nodes at distance 3?
5
2 2 0
 6

How Does BSF Work?

• Similarly to level-order traversal for trees.

• The BFS code we will discuss works for both directed and
undirected graphs.

• Animation:
• BFS: https://www.youtube.com/watch?v=x-VTfcmrLEQ
• DFS: https://www.youtube.com/watch?v=NUgMa5coCoE
 7

Skeleton of BFS Algorithm

output v;

Note: We may visit a vertex more than once. The next slide solves this problem.
 8

BFS Algorithm

// flag[ ]: visited (true) or not (false)

output v;
 9

BFS Example Adjacency List Visited Table (T/F)

0 F
1 F
0
2 F
8 3 F
4 F
source 2 9 5 F

1 6 F
7 F
3 7 8 F
6 9 F
4
5
Initialize “visited”
table all to false

Q= { }

Initialize Q to be empty
 10

Example (2) Adjacency List Visited Table (T/F)

0 F
1 F
0
2 T
8 3 F
4 F
source 2 9 5 F

1 6 F
7 F
3 7 8 F
6 9 F
4
5
Flag that 2 has
been visited

Q= { 2 }

Place source 2 on the queue

 11

Example (3) Adjacency List Visited Table (T/F)

0 F
1 T
0
2 T
Neighbors
8 3 F
4 T
source 2 9 5 F

1 6 F
7 F
3 7 8 T
6 9 F
4
5
Mark neighbors
as visited 1, 4, 8

Q = {2} → { 8, 1, 4 }
Dequeue 2.
Place all unvisited neighbors of 2 on the queue
 12

Example (4) Adjacency List Visited Table (T/F)

0 T
1 T
0
2 T
8 3 F
4 T
source 2 9 5 F

1 6 F
7 F
3 7 8 T
Neighbors
6 9 T
4
5
Mark newly visited
neighbors 0, 9

Q = { 8, 1, 4 } → { 1, 4, 0, 9 }

Dequeue 8.
-- Place all unvisited neighbors of 8 on the queue.
-- Notice that 2 is not placed on the queue again, it has been visited!
 13

Example (5) Adjacency List Visited Table (T/F)

0 T
1 T
0 Neighbors
2 T
8 3 T
4 T
source 2 9 5 F

1 6 F
7 T
3 7 8 T
6 9 T
4
5
Mark newly visited
neighbors 3, 7

Q = { 1, 4, 0, 9 } → { 4, 0, 9, 3, 7 }

Dequeue 1.
-- Place all unvisited neighbors of 1 on the queue.
-- Only nodes 3 and 7 haven’t been visited yet.
 14

Example (6) Adjacency List Visited Table (T/F)

0 T
1 T
0
2 T
8 3 T
4 T
Neighbors
source 2 9 5 F

1 6 F
7 T
3 7 8 T
6 9 T
4
5

Q = { 4, 0, 9, 3, 7 } → { 0, 9, 3, 7 }

Dequeue 4.
-- 4 has no unvisited neighbors!
 15

Example (7) Adjacency List Visited Table (T/F)

0 T
Neighbors
1 T
0
2 T
8 3 T
4 T
source 2 9 5 F

1 6 F
7 T
3 7 8 T
6 9 T
4
5

Q = { 0, 9, 3, 7 } → { 9, 3, 7 }

Dequeue 0.
-- 0 has no unvisited neighbors!
 16

Example (8) Adjacency List Visited Table (T/F)

0 T
1 T
0
2 T
8 3 T
4 T
source 2 9 5 F

1 6 F
7 T
3 7 8 T
6 Neighbors 9 T
4
5

Q = { 9, 3, 7 } → { 3, 7 }

Dequeue 9.
-- 9 has no unvisited neighbors!
 17

Example (9) Adjacency List Visited Table (T/F)

0 T
1 T
0
2 T
8 3 T
Neighbors
4 T
source 2 9 5 T

1 6 F
7 T
3 7 8 T
6 9 T
4
5
Mark new visited
Vertex 5

Q = { 3, 7 } → { 7, 5 }

Dequeue 3.
-- place neighbor 5 on the queue.
 18

Example (10) Adjacency List Visited Table (T/F)

0 T
1 T
0
2 T
8 3 T
4 T
source 2 9 5 T

1 6 T
Neighbors 7 T
3 7 8 T
6 9 T
4
5
Mark new visited
Vertex 6

Q = { 7, 5 } → { 5, 6 }

Dequeue 7.
-- place neighbor 6 on the queue
 19

Example (11) Adjacency List Visited Table (T/F)

0 T
1 T
0
2 T
8 3 T
4 T
source 2 9 Neighbors 5 T

1 6 T
7 T
3 7 8 T
6 9 T
4
5

Q = { 5, 6} → { 6 }

Dequeue 5.
-- no unvisited neighbors of 5
 20

Example (12) Adjacency List Visited Table (T/F)

0 T
1 T
0
2 T
8 3 T
4 T
source 2 9 5 T
1 Neighbors 6 T
7 T
3 7
8 T
6
4 9 T
5

Q= {6}→{ }

Dequeue 6.
-- no unvisited neighbors of 6
 21

Example (13) Adjacency List Visited Table (T/F)

0 T
1 T
0
2 T
8 3 T
4 T
source 2 9 5 T

1 6 T
7 T
3 7 8 T
6 9 T
4
5

What did we discover?

Look at “visited” tables.

Q= { } Q is empty!!! STOP!!!
There exists a path from source
vertex 2 to all vertices in the graph
 22

Running Time of BFS

• Assume adjacency list
• V = number of vertices; E = number of edges

Each vertex will enter Q at

most once. dequeue is O(1).
The for loop takes time
proportional to deg(v).
 23

Running Time of BFS (2)

• Recall: Given a graph with E edges

Σvertex v deg(v) = 2E
• The total running time of the while loop is:

O( Σvertex v (1 + deg(v)) ) = O(V+E)

• This is the sum over all the iterations of the while loop!

• Homework: What is the running time of BFS if we use an adjacency matrix?

 24

BFS and Unconnected Graphs

A graph may not be connected
(strongly connected)  enhance
P the above BFS code to
Q
N accommodate this case.
L R
O
M D s
E

C
A
F
B
K
G A graph with 3 components
H
 25

Recall the BFS Algorithm …

output ( v );
 26

Enhanced BFS Algorithm

• We can re-use the previous BFS(s)
A graph with 3 components method to compute the connected
components of a graph G.
N
L BFSearch( G ) {
k = 1; // component number
M for every vertex v
flag[v] = false;
for every vertex v
C
if ( flag[v] == false ) {
A
print ( “Component ” + k++ );
B BFS( v );
K }
}
H
 27

Applications of BFS
What can we do with the BFS code we just • Is an undirected graph connected?
discussed? • Scan array flag[ ].
• If there exists flag[u] = false …
• To output the contents (e.g., the vertices) of
a connected graph
• To output the contents of a strongly
• What if the graph is not connected?
connected graph
• Use slide 25.
• What if the graph is not connected or
weakly connected?
• Is there a path from source s to a vertex v? • Use slide 25.
• Check flag[v].
 28

Appendix: Other Applications of BFS

• To find the shortest path from a vertex s to a vertex v in an unweighted graph

• To find the length of such a path

• To find out if a graph contains cycles

• To find the connected components of a graph that is not connected (slide 25)

• To construct a BSF tree/forest from a graph

 29

Next Lectures
• Depth First Search (DFS)
• Review for final exam