CSCE411 Exam 2 - Breadth First Search

BFS Description

Finds the shortest path from source node s to every other v ∈ V.

1. Initialize all nodes to have NIL parent, ∞ dist, U status

2. Initialize s to have 0 dist, D status

3. Initialize a queue Q and add s to it

4. While the queue is not empty, dequeue a vertex

5. Iterate through all adjacent edges and set their status, parent, and distance

6. Mark the node as explored and continue

BFS Pseudocode

for v ∈ V do
	v.parent = NIL
	v.dist = ∞
	v.status = U
end for
s.dist = 0
s.status = D

Initialize Q
Enqueue(s)
while |Q| > 0 do
	u = Dequeue(Q)
	N(u) = Adj[u]
	for v in N(u) do
		if v.status == U then
			v.status = D
			v.parent = i
			v.dist = u.dist + 1
			Enqueue(v)
		end if
	end for
	u.status = E
end while

BFS Analysis

Every edge and vertex is visited once, O(V+E)

BFS Benefits

BFS’s primary usecases are

1. Finding shortest paths

2. Finding connected components

3. Creating a predecessor and a BFS tree

BFS and Shortest Paths

BFS tells us the minimum distance between s and every other node in the graph.

BFS and Connected Components

If G is undirected, BFS finds the connected component that s belongs to.

BFS and Trees

BFS will return a predecessor tree G = (V,E) such that

V = { s } ∪ { v ∈ V | v.parent ≠ NIL }
E = { (v.parent, v) : v ∈ V - {s} }

BFS will also return a BFS tree.