Graphs Traversal/Searching

Posted By on November 5, 2014

Download PDF
Introduction to Graphs
Breadth First Search (BFS)

Graph Traversal

To traverse a graph is to process every node in the graph exactly once. Because there are many paths leading from one node to another, the hardest part about traversing a graph is making sure that you do not process some node twice. There are two general solutions to this difficulty:

  1. when you first encounter a node, mark it as REACHED. When you visit a node, check if it’s marked REACHED; if it is, just ignore it. This is the method our algorithms will use.
  2. when you process a node, delete it from the graph. Deleting the node causes the deletion of all the arcs that lead to the node, so it will be impossible to reach it more than once.

At the heart of our traversal algorithm – and in fact all of our algorithms – is a list of nodes that we have reached but not yet processed. we will call this the READY list.

General Traversal Strategy

  1. Mark all nodes in the graph as NOT REACHED.
  2. pick a starting node. Mark it as REACHED and place it on the READY list.
  3. pick a node on the READY list. Process it. Remove it from READY. Find all its neighbours: those that are NOT REACHED should marked as REACHED and added to READY.
  4. repeat 3 until READY is empty.
Introduction to Graphs
Breadth First Search (BFS)

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby