What is a Graph Traversal Algorithm?
Graph traversal is a search technique for finding a vertex in a graph. In the search process, graph traversal is also used to determine the order in which it visits the vertices. Without producing loops, a graph traversal finds the edges to be employed in the search process.
There are two methods to traverse a graph data structure:
• Depth-First Search or DFS algorithm
• Breadth-First Search or BFS algorithm
Following your understanding of graph traversal, you will learn about the depth-first search algorithm.
What is DFS?
The Depth First Search algorithm is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking.
Here, the word backtrack means that when you are moving forward and there are no more nodes along the current path, you move backward on the same path to find nodes to traverse. All the nodes will be visited on the current path till all the unvisited nodes have been traversed after which the next path will be selected.
This recursive nature of DFS can be implemented using stacks.
The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.
The DFS algorithm works as follows:
• Start by putting any one of the graph's vertices on top of a stack.
• Take the top item of the stack and add it to the visited list.
• Create a list of that vertex's adjacent nodes. Add the ones which are not in the visited
list to the top of the stack.
• Keep repeating steps 2 and 3 until the stack is empty.
Complexities
Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Auxiliary Space: O(V), since an extra visited array of size V is required.
Implementation
#include <iostream>
#include <vector>
using namespace std;
// Function to perform DFS recursively
void DFS(int node, vector<int> adj[], vector<bool>& visited) {
visited[node] = true;
cout << node << " ";
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
DFS(neighbor, adj, visited);
}
}
}
// Function to initialize and start DFS traversal
void startDFS(int startNode, vector<int> adj[], int numNodes) {
vector<bool> visited(numNodes, false);
DFS(startNode, adj, visited);
}
int main() {
// Create adjacency list for the graph
vector<int> adjList[5];
adjList[0] = {1, 2};
adjList[1] = {0, 2, 3};
adjList[2] = {0, 1, 3};
adjList[3] = {1, 2, 4};
adjList[4] = {3};
// Perform DFS traversal starting from node 0
cout << "DFS traversal starting from node 0: ";
startDFS(0, adjList, 5);
cout << endl;
return 0;
}
Output
DFS traversal starting from node 0: 0 1 2 3 4
Explanation
In this example, we define two functions: DFS to actually traverse the graph using depth-first search, and start DFS to initialize the visited array and begin the traversal at a specified start node.
We then use started with a starting node of 0, generate an adjacency list to represent the graph and execute it. The program outputs a DFS traversal beginning at node 0, in this case, 0 1 2 3 4.
Advantage
• Memory requirement is only linear with respect to the search graph. This is in contrast
with the breadth-first search which requires more space. The reason is that the algorithm only needs to store a stack of nodes on the path from the root to the current node.
• The time complexity of a depth-first Search to depth d and branching factor b (the
number of children at each node, the outdegree) is O(bd) since it generates the same set of nodes as breadth-first search, but simply in a different order. Thus, practically depth-first search is time-limited rather than space-limited.
• If the depth-first search finds a solution without exploring much in a path then the time
and the space it takes will be very less.
• DFS requires less memory since only the nodes on the current path are stored. By
chance, DFS may find a solution without examining much of the search space at all.
Disadvantage
• Not Guaranteed that it will give you a solution.
• The cut-off depth is smaller so the time complexity is more.
• Determination of depth until the search has proceeded.
Application
• Detecting a graph's cycle: A graph has a cycle if and only if a back edge is visible during
DFS. As a result, you may run DFS on the graph to look for rear edges.
• Finding Strongly Connected Components in a Graph: A directed graph is strongly
connected if each vertex in the graph has a path to every other vertex.
• Solving mazes and other puzzles with only one solution: By only including nodes in the
current path in the visited set, DFS is used to locate all keys to a maze.
• Path Finding: The DFS algorithm can be customized to discover a path between two
specified vertices, a, and b.
Key Difference between BFS and DFS
• BFS finds the shortest path to the destination, whereas DFS goes to the bottom of a
subtree, then backtracks.
• The full form of BFS is Breadth-First Search, while the full form of DFS is Depth-First
Search.
• BFS uses a queue to keep track of the next location to visit. whereas DFS uses a stack to keep track of the next location to visit.
• BFS traverses according to tree level, while DFS traverses according to tree depth.
• BFS is implemented using a FIFO list; on the other hand, DFS is implemented using a
LIFO list.
• In BFS, you can never be trapped in finite loops, whereas in DFS, you can be trapped in
infinite loops.