[prev] 24 [next]

Digraph Traversal

Same algorithms as for undirected graphs:

depthFirst(v):

  1. mark v as visited
  2. for each (v,w)edges(G) do
       if w has not been visited then
          depthFirst(w)


breadth-first(v):

  1. enqueue v
  2. while queue not empty do
       dequeue v
       if v not already visited then
          mark v as visited
          enqueue each vertex w adjacent to v