dfs Algorithm
The Depth First Search (DFS) algorithm is a powerful and widely-used graph traversal technique in computer science and programming. The DFS Recursive Algorithm, as the name suggests, employs recursion to explore all the vertices and edges of a graph or a tree in a depthward motion, moving as far as possible along a branch before backtracking. This algorithm can be used for various applications, such as finding connected components in an undirected graph, topological sorting in directed acyclic graphs, and solving puzzles like mazes and game boards.
In the DFS Recursive Algorithm, the traversal starts from a source node or vertex and continues to visit adjacent, unvisited vertices recursively. During the process, each visited vertex is marked as visited to avoid revisiting it in the future. Once the algorithm reaches a vertex with no unvisited neighbors, it backtracks and moves on to the next unvisited adjacent vertex in the previous node. This process continues until all reachable vertices from the source node have been visited. The DFS Recursive Algorithm can be implemented using stack data structure, where the vertices are pushed onto the stack as they are visited, and popped from the stack when backtracking. The algorithm is efficient in terms of memory usage, as it only needs to store the current path and visited vertices, making it suitable for large graphs and complex problems.
//
// Depth-first search algorithm implementation in C++
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/graphs/
// https://github.com/allalgorithms/cpp
//
// Contributed by: Nikunj Taneja
// Github: @underscoreorcus
//
#include<iostream>
#include<list>
using namespace std;
// Graph class represents a directed graph
// using adjacency list representation
class Graph
{
int V;
list<int> *adj;
void DFSUtil(int v, bool visited[]);
public:
Graph(int V);
void addEdge(int v, int w);
void DFS(int v);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
cout << v << " ";
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
void Graph::DFS(int v)
{
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(v, 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 (starting from vertex 2)\n";
g.DFS(2);
return 0;
}
