Depth-First Search (DFS)
Introduction to Graphs DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Depth-First Search (DFS) Traversal of an Undirected Graph, Recursion, Graph, Adjacency List, Depth-First Search, Undirected Graph, Graph Traversal, Time Complexity, Space Complexity, graph representation, space complexity, visited tracking, backtracking, dfs, recursion, time complexity analysis.
Depth First Search (DFS) Traversal Problem Statement Given an undirected graph and a starting node, traverse the graph using Depth First Search (DFS) and return a list containing all nodes in the order they are visited. Input Specification The first line contains two integers, V and E, representing the number of vertices and the number of edges in the graph, respectively. The next E lines each contain two integers, u and v, representing an undirected edge between node u and node v. The last line contains a single integer, S, representing the starting node for the DFS traversal. Output Specification Return a list of integers representing the nodes visited in DFS order, starting from node S. Constraints No explicit constraints were provided in the original content. Sample Test Cases Sample 1: Input: Output: Explanation: The graph has 5 nodes (0 to 4) and 4 edges. Starting DFS from node 0: 1. Visit 0. Mark 0 as visited. Explore neighbors of 0. 2. From 0, explore 2. Visit 2. Mark 2 as visited. Explore neighbors of 2. 3. From 2, explore 4. Visit 4. Mark 4 as visited. Explore neighbors of 4. (No unvisited neighbors). 4. Backtrack to 2. No more unvisited neighbors from 2. 5. Backtrack to 0. Explore 1. Visit 1. Mark 1 as visited. Explore neighbors of 1. (No unvisited neighbors). 6. Backtrack to 0. Explore 3. Visit 3. Mark 3 as visited. Explore neighbors of 3. (No unvisited neighbors). 7. Backtrack to 0. No more unvisited neighbors from 0. All reachable nodes visited in order: 0, 2, 4, 1, 3.