Depth First Search – Traversal Of The Graph

Problem Statement

Given an undirected, unweighted graph print the DFS traversal of the graph.

Sample Test Cases
Input 1:

Output 1: 0 1 2 3 4

Input 2:

Output 2: 0 1 2 3 4

Algorithm

The DFS is a backtracking-based algorithm that performs the traversal of a graph by exhaustively traversing all nodes by going ahead if possible, else by backtracking. By backtracking, it is meant that we are moving forward on the current path, till there are no nodes remaining unvisited on that path, and then we recursively move onto some other unvisited path.

The algorithm is described as follows:

• Start from any node, say root node.
• Mark the current node as visited.
• For all the immediate children of the node, if that child is not visited, recursively call the function for the child.

The above picture shows how the DFS algorithm will traverse the graph if implemented according to the above steps.

C++ Code

void dfs(int node, vector<vector<int>> &vec, vector<bool> &vis) {
    vis[node] = true;
    cout << node << " ";
    for(auto x: vec[node]) {
        if(!vis[x]) {
            dfs(x, vec, vis);
        }
    }
}
void solve(vector<vector<int>> &vec, vector<bool> &vis) {
    for(int i = 0; i < (int)vec.size(); i++) {
        if(!vis[i]) {
            dfs(i, vec, vis);
        }
    }
    cout << endl;
}

Java Code

import java.util.*;
class Edge
{
    int source, dest;
    public Edge(int source, int dest)
    {
        this.source = source;
        this.dest = dest;
    }
}
class Graph
{
    ArrayList<ArrayList<Integer>> adj = null;
    Graph(ArrayList<Edge> edges, int n)
    {
        adj = new ArrayList<>();
        for (int i = 0; i <n; i++) {
            adj.add(new ArrayList<>());
        }
        for (Edge edge: edges)
        {
            int src = edge.source;
            int dest = edge.dest;

            adj.get(src).add(dest);
            adj.get(dest).add(src);
        }
    }
}
public class Main {
    public static void DFS(Graph graph, int node, boolean[] visited)
    {
      visited[node] = true;
        System.out.print(node + " ");
        for (int i: graph.adj.get(node))
        {
            if (i!=0 && !visited[i]) {
                DFS(graph, i, visited);
            }
        }
    }
    public static void main(String[] args) {
        Scanner abc=new Scanner(System.in);
        int t= abc.nextInt();
        try{
            while(t!=0)
            {
                int n=abc.nextInt();
                int m=abc.nextInt();

                ArrayList<Edge> edges=new ArrayList<>();
                for(int i=0;i<m;i++)
                {
                    int x=abc.nextInt();
                    int y=abc.nextInt();
                    x--;
                    y--;
                    edges.add((new Edge(x,y)));
                }
                Graph graph = new Graph(edges, n+1);
                boolean[] visited= new boolean[n+1];
                for (int i = 1; i <= n; i++)
                {
                    if  (!visited[i]){
                        DFS(graph, i, visited);
                    }
                }
                t--;
            }
        }catch(Exception E)
        {
            return;
        }
    }
}

Python Code

def dfs(node, vec, vis):
    vis[node] = True
    print(node, end = " ")
    for ele in vec[node]:
        if not vis[ele]:
            dfs(ele, vec, vis)

def solve(vec, vis):
    for i in range(len(vec)):
        if not vis[i]:
            dfs(i, vec, vis)
    print()

Time Complexity: O(|V| + |E|) // V = number of vertices, E = number of edges
Space Complexity: O(|V|)

Practice Problem – Cycle in Undirected Graph

FAQs

Q.1: Can DFS be used for finding the shortest path in a graph?

Ans. DFS cannot be used for finding the shortest path in a graph. For that problem, we need to use Breadth-First Search(BFS).

Q.2: What are some of the problems that can be solved using DFS?

Ans. Counting the number of connected components in a graph, Detecting the cycle in an undirected graph, Finding topological sorting of a graph, etc, are some of the applications of the DFS algorithm.