Depth-First-Search(DFS) Explained With Visualization

Photo by Benjamin Elliott on Unsplash

DFS Overview

The Depth First Search(DFS) is the most fundamental search algorithm used to explore the nodes and edges of a graph. It runs with time complexity of O(V+E), where V is the number of nodes, and E is the number of edges in a graph.

DFS is often used as a building block in other algorithms; it can be used to:

1. A naive solution for any searching problem.
2. Finding connected components or strongly connected components.
3. Topological sorting.
4. Finding the bridges of a graph.
5. Detect cycles in a graph.

DFS Visualization on Maze

The source is at the position of left-up, and the target is the position of right-bottom.

As we can see, DFS explores as far as possible along each branch before backtracking:

The maze is generated by disjoint set.

The recursive implementation

#include <list>
#include <vector>
#include <iostream>
using namespace std;