Depth- First Search Algorithm
The Depth-First Search (DFS) algorithm is a traversing technique used for exploring graphs or trees. It is an approach that works by visiting each vertex of a graph and exploring as far as possible before backtracking to explore other vertices. DFS begins at the starting node or root vertex and follows the path along the edges until it reaches a leaf node or a dead-end. Once it cannot go any further, the algorithm backtracks and continues the search from the last unexplored neighboring node. This process is repeated until all the vertices in the graph or tree have been visited.
DFS can be implemented using either recursion or an explicit stack data structure. In the recursive approach, the algorithm calls itself for each unvisited neighboring vertex, effectively utilizing the call stack. On the other hand, the explicit stack implementation involves maintaining a stack of vertices to visit, with each iteration popping a vertex from the stack and exploring its neighbors. The DFS algorithm is particularly useful for solving problems related to connectivity, pathfinding, and topological sorting. It is also employed as a fundamental building block in several other graph algorithms, such as finding strongly connected components, detecting cycles, and solving puzzles like mazes.
/*
Petar 'PetarV' Velickovic
Algorithm: Depth-First Search
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
#define MAX_N 5001
using namespace std;
typedef long long lld;
struct Node
{
vector<int> adj;
};
Node graf[MAX_N];
bool mark[MAX_N];
//Algoritam za pretrazivanje grafa u dubinu
//Slozenost: O(V + E)
inline void DFS(int start)
{
stack<int> dfs_stek;
dfs_stek.push(start);
while (!dfs_stek.empty())
{
int xt = dfs_stek.top();
dfs_stek.pop();
mark[xt] = true;
printf("Traversing Node ID %d\n", xt);
for (int i=0;i<graf[xt].adj.size();i++)
{
if (!mark[graf[xt].adj[i]])
{
dfs_stek.push(graf[xt].adj[i]);
mark[graf[xt].adj[i]] = true;
}
}
}
}
int main()
{
graf[0].adj.push_back(1);
graf[0].adj.push_back(2);
graf[2].adj.push_back(3);
graf[3].adj.push_back(4);
DFS(0);
return 0;
}
