Graph Traversal in Data Structure

A graph, a non-linear data structure represented by vertices (nodes) and edges, is defined as an ordered set (V, E) where V represents the set of vertices and E represents the set of edges connecting these vertices. Every pair of vertices is connected by one edge. Graph traversal, a fundamental operation in graph theory and computer science, involves systematically visiting all nodes in a graph. This graph traversal process is crucial in various applications such as network routing, web crawling, and social network analysis.

Methods of Graph Traversal in Data Structure

In simple words, traversal means the process of visiting every node in the graph. There are two standard methods of graph traversal in data structure Breadth-First Search and Depth First Search

BFS Graph Traversal

Breadth-First Search (BFS) is a graph traversal algorithm, where we start from a selected(source) node and traverse the graph level by level, by exploring the neighbor nodes at each level.

Algorithm

Breadth-First Search (BFS) is a crucial algorithm for graph traversal, prioritizing the exploration of a node's immediate neighbors before advancing to their next-level neighbors. This strategy enables efficient searching for the shortest paths in unweighted graphs and ensures all nodes are visited systematically, starting from the closest. Employing a FIFO queue, BFS initiates from a chosen source node, exploring and marking each node by visiting adjacent unvisited ones, adding them to the queue for subsequent exploration. This process continues until the queue empties, signifying the completion of traversal.

Let's see how to use a Breadth-First Search from Node A.

We need to use two data structures a Queue (for FIFO property) and a Set visited (to mark the visited nodes).

Step: 1 We pick A as the starting point and add A to the Queue. To prevent cycles, we also mark A as visited(by adding it to the visited set).

Step: 2 We remove the head of the Queue (i.e. A now). The Node was First In (inserted first) in the Queue. We process A and pick all its neighbours that have not been visited yet(i.e., not in the visited set). Those are D, C, and E. We add D, C, and E to the Queue and these to the visited set.

Step :3 Next, we pull the head of the Queue, , i.e. D. We process D and consider all neighbours of D, which are A and E, but since both A and E are in the visited set, we ignore them and move forward.

Step :4 Next, we pull the head of the Queue, i.e. E. We process E. Then we need to consider all neighbours of E, which are A and D, but since both A and D are in the visited set, we ignore them and move forward.

Next, we pull the head of the Queue, i.e. C. We process C. Then we consider all neighbours of C, which are A and B. Since A is in the visited set, we ignore it. But as B has not yet been visited, we visit B and add it to the Queue.

Step 5: Finally, we pick B from Queue, and its neighbour is C, which has already visited. We have nothing else in Queue to process, so we are done traversing the graph.

So the order in which we processed/explored the elements are: A, D, E, C, B which is the Breadth-First Search of the above Graph.

Pseudocode of Breadth-First Search

Code Implementation

Output:

DFS Graph Traversal

Depth First Search (DFS) is a graph traversal algorithm, where we start from a selected(source) node and go into the depth of this node by recursively calling the DFS function until no children are encountered. When the dead-end is reached, this algorithm backtracks and starts visiting the other children of the current node.

Algorithm

Let's see how we can approach the depth first search algorithm.

We can start our DFS process from any arbitrary vertex of the graph. Suppose we start our depth first search process from vertex A, since need to go as deep as possible in the graph, therefore we will go to one of the adjacent vertices of A.

The only thing we must take care of during the DFS process is that "we must not visit already visited vertices again."

• We have two choices i.e. either to go to vertex B or vertex D. Let's say we went to vertex B now again we will go to one of its adjacent vertices.
• We are having three choices i.e. either to go to vertex C or vertex E or back to vertex A (because A is also adjacent to vertex B ) but we will consider going A again because we had already visited it. Let's say we went to vertex E, again from E we need to go to one of its adjacent vertices.
• Now at E we have three choices i.e. either to go to vertex F or vertex G or vertex B back but we will not consider it because it is already visited. Let's say we went to vertex F.
• From vertex F we have only one unvisited node left i.e. vertex G, so we will visit it.
• We don't have any unvisited vertex adjacent to G so we will go back to F.
• Now from F also we don't have any choice so we will go back to E and from E the case is the same again so we will go back to B.
• From B we have C as an unvisited adjacent vertex so we will go to vertex C and then from C we will go to vertex D as it is unvisited till now.
• You can see now all the vertices have been traversed in the following order --A→B→E→F→G→C→D.

Pseudocode of DFS Algorithm

Code Implementation

Output: