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:
- A naive solution for any searching problem.
- Finding connected components or strongly connected components.
- Topological sorting.
- Finding the bridges of a graph.
- 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;
class Graph {
int V;
list<int> *adj;
bool DFS_rec(int v, int t, vector<bool>& visited);
public:
Graph(int V);
void addEdge(int v, int w);
bool DFS(int v, int t);
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
bool Graph::DFS_rec(int v, int t, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
if(v == t) return true; // Find a path
for (list<int>::iterator it; it = adj[v].begin(); it != adj[v].end(); ++it) {
if (!visited[*it] && DFS_rec(*it, t, visited))
return true;
}
return false;
}
bool Graph::DFS(int v, int t) {
vector<bool> visited(V, false);
return DFS_rec(v, t, visited);
}
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Depth First Traversal (0 -> 3): \n";
if(g.DFS(0, 3)) cout << "\nFind a Path!" << std::endl;
else cout << "\nNo Path!" << std::endl;
return 0;
}
The iterative implementation
A non-recursive implementation of DFS needs the data-structure of stack.
The worst-case space complexity is O(E).
bool Graph::DFS(int v, int t) {
vector<bool> marked(V, false);
stack<int> S;
S.push(v);
marked[v] = true;
while(!S.empty()) {
int n = S.top(); S.pop();
cout << n << " ";
if(n == t) //Find a path to target
return true;
for(list<int>::iterator it = adj[n].begin(); it != adj[n].end(); ++it) {
if(!marked[*it]) {
marked[*it] = true;
S.push(*it);
}
}
}
return false;
}
References
- C: Algorithms
- Java: Data Structures and Abstractions with Java
- Python：Problem Solving with Algorithms and Data Structures Using Python
The post Depth-First-Search(DFS) Explained With Visualization appeared first on CodersCat.
Top comments (1)
Great Article!!
I'm doing a large work to create a comprehensive header-only library for C++ for graph Representation, Manipulation, Partitioning and Algorithms.
I'm looking for Contributor, but also a simple feedback is good enough.
If you have 5 min to check my repo I'd be very grateful.
Header-Only C++ Library for Graph Representation and Algorithms
CXXGraph
Table of Contents
Introduction
CXXGraph is a small library, header only, that manages the Graph and it's algorithms in C++. In other words a "Comprehensive C++ Graph Library".
Algorithm Explanation
Dijkstra
Graph Dijkstras Shortest Path Algorithm(Dijkstra's Shortest Path) Dijkstra's Algorithm is used to find the shortest path from a source node to all other reachable nodes in the graph. The algorithm initially assumes all the nodes are unreachable from the given source node so we mark the distances of all nodes as infinity (infinity) from source node (INF / infinity denotes unable to reach).
Dial
Dial specialization of dijkstra’s algorithm.
When edge…
Thank you so much in advance.
Best regards