ML Wiki

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)$

Applications

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.

why?

• 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

• Graphs
• Graph Search и Depth-First Search
• Dijkstra's Shortest Path

Sources

• Algorithms Design and Analysis Part 1 (coursera)