CITS2200 - Lecture 21

← Back to Home

CITS2200 - Lecture 20
Breadth-First Search - Slides

Breadth-First Search

• Breadth-First Search (BFS) is a traversal technique that explores rooted trees and graphs layer by layer
  • Vertices are separated in different levels
  • Begins at a starting vertex

As BFS explores, edges get classified:

• Discovery edge $-$ leads to an unexplored vertex
• Cross edge $-$ connects two already-visited vertices at the same or adjacent level

---

Properties of BFS

• Property 1 $-$ $BFS(G,s)$ visits all vertices and edges in the connected component of $s$
• Property 2 $-$ discovery edges form a spanning tree of connected component of $s$
• Property 3 $-$ every vertex in $L_i$ has a shortest path of exactly $i$ edges from $s$; BFS guarantees shortest paths between vertices
  • $L_i$ $-$ Level $i$

Complexity Analysis of BFS

Assuming we are using an adjacency list representation:

Operation	Cost
Label a vertex or edge	$O(1)$
Each vertex labeled twice (UNEXPLORED → VISITED)	$O(n)$ total
Each edge labeled twice	$O(m)$ total
incidentEdges called once per vertex	$O(m)$ total
Total	$O(n+m)$
Identical to [[CITS2200 - Lecture 20#Depth-First Search	DFS]]

---

Applications of BFS

• Shortest path $-$ given two vertices, find the path between them with the minimum number of edges or report no path exists
• Find a simple cycle or report that graph is a forest

---

DFS vs BFS

• DFS follows the path as deep as possible
  • Back edges indicate cycles
• BFS spreads level by level
  • Cross edges connect vertices at same or adjacent levels
  • Finds the shortest path (by edge count) between vertices

---

CITS2200 - Lecture 22