Graph Traversal Algorithms

  • Breadth-first: using queues
  • Depth-first: using stacks

Breadth-first

Given graph $G$, starting node $n_0$ and a vector $visited$:

  • Start from node $n_0$, push into queue
  • Repeat until queue is empty
    • pop one element from queue
    • push the unvisited adjacent nodes of the poped element into the queue, and marked them visited

In [ ]: