Traversal in Graph

Introduction of Traversal in Graph

• Traversal means the act or process of passing across, over, touching, or through and doing something with the data.
• A graph traversal technique visits every node exactly once in a systematic fashion.

Definition

• Graph traversal is a process for accessing/searching all the vertices data values as needed in a graph.

Characteristics

• Graph traversal algorithms typically begin with a start vertex and attempt to visit the remaining vertices from there in a certain order. 

Types

• There are two types of graph traversal techniques commonly found in the graph. They are as follows: –

1. DFS (Depth First Search) Traversal
2. BFS (Breadth First Search) Traversal

Depth First Search(DFS) Traversal :

• DFS traversal of a graph produces a spanning tree(a graph without loops/cycles) as the final result.
• The implementation of DFS involves a Stack data structure with a maximum size of the total number of vertices in the graph.
• In the DFS traversal approach, the traverse begins from/at the root node and proceeds through the connected nodes as far as possible up to the highest depth node sequentially, and then we reach the remaining branched nodes with no unvisited nearby nodes one by one.
• Depth-first search is used in topological sorting, scheduling processes, cycle detection in graphs, and solving puzzles with only one solution.
• DFS is faster than BFS comparatively.
• DFS works better in traversal when the target/searching value is far from the source.
• The DFS traversal needs less memory comparatively as it only has to keep track of the nodes in a chain from the top to the bottom, while the BFS has to keep track of all the nodes on the same level.

Breadth First Search(BFS) Traversal :

• BFS traversal of a graph produces a spanning tree(a graph without loops/cycles) as the final result.
• In BFS traversal, we first walk through all nodes on the same level from left to right before moving on to the next level(i.e. top to bottom level).
• The implementation of BFS involves a Queue data structure with a maximum size of the total number of vertices in the graph.
• BFS is slower than BFS comparatively.
• BFS works better in traversing when the target value is closer to the Source.
• As BFS considers all neighbors during traversal it is not suitable for decision trees used in the making of puzzle games.
• The concept of BFS is used to find all neighboring locations in a GPS navigation system, Broadcast the data packets in a Network, Garbage Collection work, etc.

Use/Application

• The process of graph traversal is used to search/access specific/all data items in a certain specific order from the vertex of a graph.