Graph Traversal
In this tutorial, you will learn about the followings:
- What is Graph Traversal in Data Structure?
- Types of Graph Traversal
What is Graph Traversal in Data Structure?
Graph traversal is the process of visiting all the vertices (nodes) in a graph in a systematic way. It involves exploring or traversing each vertex in a graph by following the edges that connect the vertices.
There are two common methods for graph traversal: Breadth-First Search (BFS) and Depth-First Search (DFS). BFS explores all the neighboring nodes at the current depth before moving on to nodes at the next depth level, while DFS explores the deepest vertices of a graph before backtracking to explore other vertices.
Graph traversal is used in many graph algorithms, such as finding the shortest path between two vertices, checking if a graph is connected, finding cycles in a graph, and more. By visiting all the vertices in a graph, graph traversal helps to uncover the structure and properties of the graph, which can be used to solve various problems.
Types of Graph Traversal
There are two common methods for graph traversal: Breadth-First Search (BFS) and Depth-First Search (DFS).
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
Breadth-First Search (BFS)
Breadth-First Search (BFS) is a graph traversal algorithm that explores all the neighboring nodes at the current depth before moving on to nodes at the next depth level. It starts at the root node (or any other randomly chosen node) and explores all the vertices in the graph.
The BFS algorithm uses a queue data structure to keep track of the nodes to visit.
Breadth-First Search (BFS) Algorithm
Step 1: Define a queue with the same number of nodes as the graph.
Step 2: Start traversal from starting point and put it into the Queue and count it as visited.
Step 3: Enqueue all the neighboring nodes of the visited node that have not been visited yet.
Step 4: When there are no more vertices to visit . Dequeue that node (front Node) from the queue.
Step 5: Repeat steps 3 and 4 until queue is empty.
Step 6: When the queue is empty, make the final spanning tree by removing unused lines from the graph.
Consider the following Graph to perform Breadth First Traversal (BFS)
