Graph traversal

From Wikibooks, open books for an open world
Jump to navigation Jump to search

PAPER 1 - ⇑ Fundamentals of algorithms ⇑

Graph traversal Tree traversal →

Breadth First traversal[edit | edit source]

  1. Enqueue the source node or nodes that make up the set of starting nodes.
  2. Dequeue a node and examine it.
    • If the element sought is found in this node, quit the search and return a result.
    • Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
  3. If the queue is empty, every node on the reachable sub-graph has been examined – quit the search and return "not found".
  4. If the queue is not empty, repeat from Step 2.

Depth First traversal[edit | edit source]

Using a stack instead of a queue would turn this algorithm into a depth-first search.

The above method described is non-recursive , so in order to do "Post Order" traversal, which is an important variation , instead of working on the current vertex after inserting all its children in the stack, insert it into a second stack. Then pop of the vertices in the second stack and operate on them in that order.

If the graph and parent-child relationships represents a dependency relationship, e.g. a construction schedule for various trades, a curriculum of related units of study, then the order created by emptying the second stack creates a viable schedule.