Breadth-First Search

A Graph Search algorithm:

  • explores Graphs in "layers"
  • uses FIFO (i.e. a queue)

Basic Algorithm

BFS(graph $G$, start vertex $s$):

  • [all nodes are initially unexplored]
  • mark $s$ as explored
  • $Q$ = queue, initialized with $s$
  • while $Q$ is not empty
    • remove $v$ from $Q$
    • for each edge $(v, w)$
      • if $w$ unexplored
      • mark $w$ as explored
      • add $w$ to $Q$

running time $O(m + n)$


Shortest Path

Goal: compute $\text{dist}(v)$ - the fewest number of edges on the path from $s$ to $v$ (in unweighted graph)

Extra code:

  • in initialization:
    • $\text{dist}(v)$:
      • $0$ if $v = s$
      • $\infty$ if $v \ne s$
  • when considering edge(v, w):
    • if $w$ unexplored
    • set $\text{dist}(w) = \text{dist}(v) + 1$

Connected Components

Goal: compute all connected components of an undirected graph.


  • is network connected?
  • graph visualization
  • clustering (quick and dirty)

ConnectedComponents(graph $G$):

  • for $i$ = 1 to $n$
  • if $i$ not exploted
    • BFS($G$, $i$)

Running time also $O(n + m)$

See also