Graph Traversal in Data Structure – Different Types with Code Examples

Updated on October 9, 2024

Article Outline

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.
*Image
Get curriculum highlights, career paths, industry insights and accelerate your technology journey.
Download brochure

Graph Traversal in Data Structure

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:

def bfs(graph, start_node): queue = [start_node] visited = set() while queue: node = queue.pop(0) if node not in visited: visited.add(node) print(node) for neighbor in graph[node]: queue.append(neighbor)

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 

from collections import deque def bfs(graph, start): visited = set() queue = deque([start]) while queue: vertex = queue.popleft() if vertex not in visited: visited.add(vertex) print(vertex) queue.extend(graph[vertex] - visited) return visited graph = { 'A': {'B', 'C'}, 'B': {'A', 'D', 'E'}, 'C': {'A', 'F'}, 'D': {'B'}, 'E': {'B', 'F'}, 'F': {'C', 'E'} } bfs(graph, 'A')

 

Output

A B C E D F

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:

def dfs(graph, start_node, visited=set()): visited.add(start_node) print(start_node) for neighbor in graph[start_node]: if neighbor not in visited: dfs(graph, neighbor, visited)

Code Implementation

def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next_vertex in graph[start] - visited: dfs(graph, next_vertex, visited) return visited graph = { 'A': {'B', 'C'}, 'B': {'A', 'D', 'E'}, 'C': {'A', 'F'}, 'D': {'B'}, 'E': {'B', 'F'}, 'F': {'C', 'E'} }  dfs(graph, 'A')

Output

A C F E B D

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.

FAQs
Graph traversal techniques are methods used to explore or visit the nodes (vertices) and edges of a graph. The most common traversal techniques are Depth First Search (DFS) and Breadth First Search (BFS).
DFS: Stack (either explicit or using the call stack in recursion). BFS: Queue for tracking nodes to visit.
To traverse all nodes in a disconnected graph, DFS and BFS must be initiated from every unvisited node, ensuring all components are explored.
Graph traversal is the systematic process of visiting all the nodes or vertices of a graph to explore or search through it.
Yes, both DFS and BFS can be used for cycle detection. In an undirected graph, cycles can be detected by checking if an adjacent node has already been visited (and is not the parent). In directed graphs, DFS can be used to detect cycles by tracking the recursion stack.

Updated on October 9, 2024

Link
left dot patternright dot pattern

Programs tailored for your success

Popular

Management

Data Science

Finance

Technology

Future Tech

Upskill with expert articles

View all
Hero Vired logo
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
Blogs
Reviews
Events
In the News
About Us
Contact us
Learning Hub
18003093939     ·     hello@herovired.com     ·    Whatsapp
Privacy policy and Terms of use

|

Sitemap

© 2024 Hero Vired. All rights reserved