Depth-first Search (DFS) Algorithm With Example

Depth First Search (DFS) With Example

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.

Aspect	Advantages	Disadvantages
Memory Requirement	Requires only linear memory with respect to the search graph, as it only stores a stack of nodes on the path from the root to the current node.	Not guaranteed to provide a solution.
Time Complexity	Time complexity to depth d and branching factor b is O(bd), as it generates the same set of nodes as breadth-first search but in a different order. DFS is generally limited by time rather than space	The cut-off depth being smaller can result in higher time complexity.
Efficiency	If a solution is found without exploring much of the path, the time and space requirements are significantly lower.	Determination of the depth is only possible after the search proceeds.
Memory Usage	Requires less memory since only the nodes on the current path are stored.
Search Space Exploration	By chance, DFS may find a solution without examining much of the search space at all.

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.

Also Read – Breadth First Search (BFS) Algorithm with Example