Breadth-First Search

Breadth-first search (BFS) is a general technique for traversing a graph

A BFS traversal of a graph G

Visits all the vertices and edges of G

Determines whether G is connected

Computes the connected components of G

Computes a spanning forest of G

BFS on a graph with n vertices and m edges takes O(n + m ) time

BFS can be further extended to solve other graph problems

Find and report a path with the minimum number of edges between two given vertices

## Analysis

Setting/getting a vertex/edge label takes O(1) time q Each vertex is labeled twice

once as UNEXPLORED

once as VISITED

Each edge is labeled twice

once as UNEXPLORED

once as DISCOVERY or CROSS

Each vertex is inserted once into a sequence Li

Method incidentEdges is called once for each vertex

BFS runs in O(n + m) time provided the graph is represented by the adjacency list structure

## Notation Gs: connected component of s

Property 1 BFS (G, s) visits all the vertices and edges of Gs

Property 2 The discovery edges labeled by BFS (G, s) form a spanning tree Ts of Gs

Property 3 For each vertex v in Li n The path of Ts from s to v has i edges n Every path from s to v in Gs has at least i edges

## Applications

q We can specialize the BFS traversal of a graph G to solve the following problems in O(n + m) time

n Compute the connected components of G

n Compute a spanning forest of G

n Given two vertices of G, find a path in G between them with the minimum number of edges, or report that no such path exists

n Check if a connected graph G is bipartite.

Written with ♥ from Mangesh.