- Problem Statement<\/a><\/li>
- C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- FAQs<\/a><\/li>
- Q.1: Can DFS be used for finding the shortest path in a graph?<\/a><\/li>
- Q.2: What are some of the problems that can be solved using DFS?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
Given an undirected, unweighted graph print the DFS traversal of the graph.<\/p>\n\n\n\n
Sample Test Cases<\/strong>
Input 1:<\/strong><\/p>\n\n\n\n<\/figure><\/div>\n\n\n\n
Output 1:<\/strong> 0 1 2 3 4<\/p>\n\n\n\n
Input 2:<\/strong><\/p>\n\n\n\n
Output 2:<\/strong> 0 1 2 3 4<\/p>\n\n\n\n
Algorithm<\/strong><\/p>\n\n\n\n
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.<\/p>\n\n\n\n
The algorithm is described as follows:<\/p>\n\n\n\n
- Start from any node, say root node.<\/li>
- Mark the current node as visited.<\/li>
- For all the immediate children of the node, if that child is not visited, recursively call the function for the child.<\/li><\/ul>\n\n\n\n
The above picture shows how the DFS algorithm will traverse the graph if implemented according to the above steps.<\/p>\n\n\n\n
C++ Code<\/h3>\n\n\n\n
void dfs(int node, vector<vector<int>> &vec, vector<bool> &vis) {\n vis[node] = true;\n cout << node << \" \";\n for(auto x: vec[node]) {\n if(!vis[x]) {\n dfs(x, vec, vis);\n }\n }\n}\nvoid solve(vector<vector<int>> &vec, vector<bool> &vis) {\n for(int i = 0; i < (int)vec.size(); i++) {\n if(!vis[i]) {\n dfs(i, vec, vis);\n }\n }\n cout << endl;\n}<\/pre>\n\n\n\nJava Code<\/h3>\n\n\n\n
import java.util.*;\nclass Edge\n{\n int source, dest;\n public Edge(int source, int dest)\n {\n this.source = source;\n this.dest = dest;\n }\n}\nclass Graph\n{\n ArrayList<ArrayList<Integer>> adj = null;\n Graph(ArrayList<Edge> edges, int n)\n {\n adj = new ArrayList<>();\n for (int i = 0; i <n; i++) {\n adj.add(new ArrayList<>());\n }\n for (Edge edge: edges)\n {\n int src = edge.source;\n int dest = edge.dest;\n\n adj.get(src).add(dest);\n adj.get(dest).add(src);\n }\n }\n}\npublic class Main {\n public static void DFS(Graph graph, int node, boolean[] visited)\n {\n visited[node] = true;\n System.out.print(node + \" \");\n for (int i: graph.adj.get(node))\n {\n if (i!=0 && !visited[i]) {\n DFS(graph, i, visited);\n }\n }\n }\n public static void main(String[] args) {\n Scanner abc=new Scanner(System.in);\n int t= abc.nextInt();\n try{\n while(t!=0)\n {\n int n=abc.nextInt();\n int m=abc.nextInt();\n\n ArrayList<Edge> edges=new ArrayList<>();\n for(int i=0;i<m;i++)\n {\n int x=abc.nextInt();\n int y=abc.nextInt();\n x--;\n y--;\n edges.add((new Edge(x,y)));\n }\n Graph graph = new Graph(edges, n+1);\n boolean[] visited= new boolean[n+1];\n for (int i = 1; i <= n; i++)\n {\n if (!visited[i]){\n DFS(graph, i, visited);\n }\n }\n t--;\n }\n }catch(Exception E)\n {\n return;\n }\n }\n}<\/pre>\n\n\n\nPython Code<\/h3>\n\n\n\n
def dfs(node, vec, vis):\n vis[node] = True\n print(node, end = \" \")\n for ele in vec[node]:\n if not vis[ele]:\n dfs(ele, vec, vis)\n\ndef solve(vec, vis):\n for i in range(len(vec)):\n if not vis[i]:\n dfs(i, vec, vis)\n print()<\/pre>\n\n\n\n
- Q.2: What are some of the problems that can be solved using DFS?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
- Java Code<\/a><\/li>
- C++ Code<\/a><\/li>
![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-1-DFS-1024x834.png\")
<\/figure><\/div>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-2-DFS.png\")
<\/figure><\/div>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/DFS-Algorithm.png\")
<\/figure><\/div>\n\n\n\n