Join Our 4-Week Free Gen AI Course with select Programs.

Request a callback

or Chat with us on

Learning Hub

Articles

Graph Traversal in Data Structure – Different Types with Code Examples

Basics of Python

5 Hrs. duration

9 Modules

1800+ Learners

Start Learning

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.

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

Internship Assurance

DevOps & Cloud Engineering

Explore

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

What are graph traversal techniques?

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).

Which data structures are commonly used in graph traversal algorithms?

DFS: Stack (either explicit or using the call stack in recursion). BFS: Queue for tracking nodes to visit.

How do DFS and BFS handle disconnected graphs?

To traverse all nodes in a disconnected graph, DFS and BFS must be initiated from every unvisited node, ensuring all components are explored.

What is graph traversal?

Graph traversal is the systematic process of visiting all the nodes or vertices of a graph to explore or search through it.

Can DFS and BFS be used for cycle detection in graphs?

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.

The DevOps Playbook

Simplify deployment with Docker containers.

Streamline development with modern practices.

Enhance efficiency with automated workflows.

Programs tailored for your success

Popular

Management

Data Science

Finance

Technology

Future Tech

3 ASSURED INTERVIEWS

Accelerator Program in

Business Analytics and Data Science

With

Part-time · 10 months

Apply by : 19 October, 2024

Financial Analysis, Valuation, & Risk Management

3 ASSURED INTERVIEWS

Certificate Program in

Financial Analysis, Valuation, & Risk Management

With

Part-time · 7 months

Apply by : 19 October, 2024

INTERNSHIP ASSURANCE

Certificate Program in

DevOps & Cloud Engineering

With

Part-time · 7.5 months

Apply by : 19 October, 2024

Upskill with expert articles

View all

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.

Data Science

Accelerator Program in Business Analytics & Data Science

Integrated Program in Data Science, AI and ML

Accelerator Program in AI and Machine Learning

Advanced Certification Program in Data Science & Analytics

Technology

Certificate Program in Full Stack Development with Specialization for Web and Mobile

Certificate Program in DevOps and Cloud Engineering

Certificate Program in Application Development

Certificate Program in Cybersecurity Essentials & Risk Assessment

Finance

Integrated Program in Finance and Financial Technologies