Purpose

The purpose of the graph traversal algorithms are two-fold.

  • First and foremost to give a reasonable wayto traverse the graphs.
  • Second to show samples of how to traverse the graphs in different ways.
  • Breadth First Traversal (BFTraversal)

  • This iterates through the graph's nodes in a breadth first order.
  • Algorithm

    This uses a queue to store child nodes. They are processes in FIFO order.

    Visit a node, putting it's children (if it has any) in the queue.

    Pop the front of the queue and process that node. Continue until the queue is empty.

    Potential Improvements:

    Keep a side set to check for multiple visitation of the same node (cycle detection).

    Depth First Traversal (DFTraversal)

  • This iterates through the graph's nodes in a depth first order.
  • Algorithm

    This uses a stack to store child nodes. They are processes in LIFO order.

    Visit a node, putting it's children (if it has any) in the stack.

    Pop the top of the queue and process that node. Continue until the stack is empty.

    Potential Improvements:

    Keep a side set to check for multiple visitation of the same node (cycle detection).