Depth-First Search Implementation

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Depth-First Search Implementation. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Implement depth-first search (DFS) for a graph or tree starting from a given node. Return the order in which nodes are first visited.

The input graph is represented as an adjacency list: a dictionary mapping each node to a list of neighboring nodes. The graph may contain cycles, so your solution must avoid revisiting nodes. If the start node is not present in the graph, return an empty list.

Functionality

Write a function that takes:

graph: a dictionary where keys are node values and values are lists of adjacent node values
start: the node to begin traversal from

Return:

a list of nodes in DFS visit order

Use either recursive or iterative DFS, but the traversal must visit each reachable node at most once.

Constraints

1 <= len(graph) <= 10^4
Each adjacency list may contain zero or more neighbors
Node values are hashable Python objects
The graph may contain cycles, self-loops, and disconnected components
The traversal should only include nodes reachable from start

Function Signature

def dfs_traversal(graph, start):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output