DFS TRAVERSAL

In a binary tree, there are three types of depth-first traversals:

Pre-order
Post-order
In-order

DFS (Depth-First Search) explores depth-wise. If there is no path forward, it backtracks and checks for other possible paths

.
DFS follows pre-order traversal in trees. We start from the root node, move to the left subtree, and visit all its nodes before moving to the right subtree. . In a tree, cycles do not exist, but in a graph, they can exist.

**Time Complexity:
**O(Vertex + Edge) = O(V + E)

**
Concepts Involved:**
DFS is based on recursion and backtracking.
We ensure that we do not visit the same node more than once.
To store the graph, we use an adjacency list.
DFS is used in applications like finding connected components, detecting cycles, and pathfinding.

BFS vs DFS:
DFS explores depth-wise, whereas
BFS (Breadth-First Search) explores level-wise..

Implementation

#include <bits/stdc++.h>
using namespace std;
vector<int> adj_list[1005];
bool vis[1005];

void dfs(int src)
{

    cout << src << " ";
    vis[src] = true;
    for (int child : adj_list[src])
    {
        if (vis[child] == false)
            dfs(child);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, e;
    cin >> n >> e;
    while (e--)
    {
        int a,b ;
        cin >> a >> b ;
        adj_list[a].push_back(b);
        adj_list[b].push_back(a);
    }
    dfs(0) ;
}