Depth First Search

Introduction:

This is one of the graph traversal algorithms. This is used in Topological sorting, kosaraju's algorithm. when graph is very big, dfs may suffer from non termination, so we can limit our traversal to certain depths only.

Problem Statement:

print the nodes of a graph G from start node such that the graph is traversed to is max possible depths before recursing back.

Algorithm

1. A graph \(G(V, E)\) and start vertex \(s\) are given.

2. We call dfs on start node .

3. Mark start node as visited .

4. For each unvisited node in one step of start node call dfs on that node.

5. All nodes reachable from start node will be printed. (Nodes that are not reachable from start node will not be printed in the above process..try to do it. ..)

Pseudo code :

visited[100] = {false};
dfs( adjacency_list, start_vertex ):
    visited[start_vertex] = true
            print(start_vertex)
    for v in adjacency_list[start_vertex]:
        if !visited[v]:
            dfs(adjacency_list, v)     // visit it

Code :

    #include <bits/stdc++.h>
    using namespace std;
    
    int visited[100] = {0};
    
    void dfs(map<int, vector<int>> &adj, int s)
    {
        visited[s] = 1;
        cout << s << " ";
        vector<int>::iterator itr;
        for (auto u : adj[s])
        {
            if (!visited[u])
            {
                dfs(adj, u);
            }
        }
    }
    
    int main()
    {
        int n;
        cin >> n;
    
        map<int, vector<int>> adj; // u - {v1, v2, .... vk}
    
        int u, v;
        for (int i = 0; i < n; i++)
        {
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int s;
        cout << "Enter start vertext for dfs : ";
        cin >> s;
        dfs(adj, s);
        cout << "\n";
    }

Complexity Analysis :

Time complexity is : \(O(|V|+|E|)\) where \(|V|\) is number of vertices and \(|E|\) is number of edges .