Graph Traversal in Data Structure – Different Types with Code Examples

Graphs are an important class of Nonlinear Data Structure. They represent entities’ connections. In graph databases, the technique of visiting all the nodes in a given graph is called the graph traversal. DFS and BFS were elaborated as the main graph traversal techniques in this article, which also includes their applications and implementation.

What is Graph Traversal?

A graph is a non-linear data structure that comprises either vertices or a collection of edges. Also, vertices may be called nodes, and edges are lines or arcs that join any two nodes in the graph. The graph is, therefore, a set of vertices (V) and a set of edges (E). It is denoted by G(V, E). It is an ideal data structure for storing and navigating through potentially large and intricate connections between two items or things.  Graph data structures are versatile structures that involve the connection of objects, making it easy to represent relationships between objects or entities.

Components of a Graph:

• Vertices: The vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertices or nodes. Every node/ vertex can be labelled or unlabeled.
• Edges: Edges are drawn or used to connect two graph nodes. It can be ordered or used as a pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labelled/unlabelled.

Operations on Graphs

Let’s discuss the basic operation of Graphs.

• Insertion of Nodes/ Edges in the graph: Insert a node into the graph.
• Deletion of Nodes/Edges in the graph: Delete a node from the graph.
• Searching on Graphs: Search an entity in the graph.
• Traversal of Graphs: Traversal all the nodes in the graph.

We can traverse a graph in two ways.

• BFS (Breadth First Search)
• DFS( Depth First Search)

BFS Graph Traversal in Data Structure

The Breadth-first search(BFS) traversal is a known method of all the nodes of a given network. This traversal algorithm picks a node and then carries the process around all the contiguous nodes. In one pass, traverse through all vertices from the start, then check all vertices from the start and then adjacent vertices in the next pass. As extra space for storing nodes for additional processing, this algorithm employs a queue as a data structure. The major measure of queue size is the maximum total number of vertices contained in the graph.

Graph Traversal: BFS Algorithm

Pseudocode:

Explanation of the above Pseudocode

• In this technique, we create a queue with the start node and an empty set to keep track of visited nodes.
• Then, it starts a loop that continues until all nodes have been visited.
• During each loop iteration, the algorithm dequeues the first node from the queue, checks if it has been visited and if not, marks it as visited, prints it or performs any other desired action, and adds all its adjacent nodes to the queue.
• This operation is repeated until the queue is empty, indicating that all nodes have been visited.

Code Implementation 

Output

DFS Graph Traversal in Data Structure

 When traversing a graph, the DFS method goes as far as possible before turning around. This algorithm explores the graph in depth-first order, starting with a given source node and then recursively visiting its surrounding vertices before backtracking. DFS will analyse the deepest vertices in a branch of the graph before moving on to other branches. To implement DFS, either recursion or an explicit stack might be utilised.

Graph Traversal: DFS Algorithm

Pseudo Code:

Code Implementation

Output

Conclusion

The technique of graph traversal is quite basic to understanding how data structures should be traversed and analysed. There are two basic techniques for searching systematically, depth-first search (DFS) and breadth-first search (BFS), each with its advantages and disadvantages. DFS is useful in searching for a particular element in a map that is hierarchical and badly connected, but it’s normally used for cycle detection and connectivity tests. BFS, on the other hand, is the best for identifying the shortest path available in the unweighted graphs and traversing through the levels systematically. These traversal methods optimise the performance to solve diverse problems inevitable in computational applications like social networks, web crawlers, and routing algorithms, not to mention artificial intelligence. Knowing when to use DFS or BFS can greatly enhance algorithm efficiency and outcome.