What is Graph Traversals ? Explain Depth First Traversal and Breadth First Traversal

Processing a graph requires the ability to traverse the graph. Traversing a graph is similar to traversing a binary tree, except that traversing a graph is a bit more complicated. Recall that a binary tree has no cycles. Also, starting at the root node, we can traverse the entire tree.

On the other hand, a graph might have cycles and we might not be able to traverse the entire graph from a single vertex (for example, if the graph is not connected). Therefore, we must keep track of the vertices that have been visited. We must also traverse the graph from each vertex (that has not been visited) of the graph.

This ensures that the entire graph is traversed. The two most common graph traversal algorithms are the depth first traversal and breadth first traversal, which are described next. For simplicity, we assume that when a vertex is visited, its index is output. Moreover, each vertex is visited only once. We use the bool array visited to keep track of the visited vertices.

Depth First Traversal

The depth first traversal is similar to the preorder traversal of a binary tree. An initial or source vertex is identified to start traversing, then from that vertex any one vertex which is adjacent to the current vertex is traversed i.e. only one adjacent vertex is traversed from the vertex which had been traversed last.

The general algorithm is:

for each vertex v in the graph

if v is not visited

start the depth first traversal at v

The general algorithm to do a depth first traversal at a given node v is:

1. Mark node v as visited

2. Visit the node

3. For each vertex u adjacent to v

a. if u is not visited

b. start the depth first traversal at u

c. Clearly, this is a recursive algorithm.

Breadth First Traversal 

The breadth first traversal of a graph is similar to traversing a binary tree level by level (the nodes at each level are visited from left to right).All the nodes at any level, i, are visited before visiting the nodes at level i + 1.

As in the case of the depth first traversal, because it might not be possible to traverse the entire graph from a single vertex, the breadth first traversal also traverses the graph from each vertex that is not visited. Starting at the first vertex, the graph is traversed as much as possible; we then go to the next vertex that has not been visited. In other words it can be stated as all vertices that are adjacent to the current vertex are traversed first. To implement the breadth first search algorithm, we use a queue.

The general algorithm is:

a.for each vertex v in the graph

if v is not visited

add v to the queue // start the breadth first search at v

b. Mark v as visited

c. while the queue is not empty

c.1. Remove vertex u from the queue

c.2. Retrieve the vertices adjacent to u

c.3. for each vertex w that is adjacent to u

if w is not visited

c.3.1. Add w to the queue

c.3.2. Mark w as visited

Example  The Depth first search for the above undirected graph

A, B, E, C, D

The Depth first search for the above undirected graph

A, B, C, D, E