Katkat
Back

Implement Depth-First Search Traversal

CadenceMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement a recursive or iterative depth-first search (DFS) while managing state to handle cycles in a graph represented as an adjacency list.

Problem Statement

You are given a graph represented as an adjacency list, where graph is a dictionary such that graph[u] is a list of all nodes v for which there is a directed edge from u to v.

Implement a function dfs_traversal(graph, start_node) that returns a list of nodes visited in the order they were first encountered during a depth-first search, starting from start_node. Your implementation must handle graphs that may contain cycles and ensure each node is visited exactly once.

Function Signature

def dfs_traversal(graph, start_node):
    # Returns: list of nodes in traversal order

Constraints

  • graph contains nodes as integers or strings.
  • The graph may be disconnected; only visit nodes reachable from start_node.
  • If a node exists in the graph but has no outgoing edges, it may not appear as a key in the dictionary; assume such nodes have an empty list of neighbors.

Examples

Example 1: Input: graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}, start_node = 2 Output: [2, 0, 1, 3] Explanation: Starting at 2, we visit 0, then from 0 we visit 1. 2 is already visited, so we backtrack and visit 3.

Example 2: Input: graph = {'A': ['B'], 'B': ['C'], 'C': []}, start_node = 'A' Output: ['A', 'B', 'C']

Edge Cases

  • Graph is empty.
  • start_node is not in the graph.
  • Graph contains a self-loop (e.g., node points to itself).

Hints

Hint 1

Use a set to keep track of visited nodes to prevent getting stuck in infinite loops during cycles.

Hint 2

Decide whether you want to implement the DFS using a recursive approach (utilizing the call stack) or an iterative approach (using an explicit stack data structure).

Hint 3

If using an iterative approach, remember that pushing neighbors onto a stack in reverse order is often necessary to match the standard recursive traversal order.

Follow-up questions

  • How would your implementation change if you needed to detect a cycle in the graph?
  • What is the time and space complexity of your solution in terms of vertices (V) and edges (E)?
  • How would you modify this to return the traversal order if there are multiple disconnected components in the graph?