At Notion, engineers often model dependencies as graphs. Implement depth-first search (DFS) on a graph and return the order in which nodes are first visited starting from a given node.
Write a function that takes an adjacency list graph and a start node. Traverse the graph using DFS, visiting neighbors in the order they appear in the adjacency list. Return a list of nodes in the order they are first visited. If the start node is not present in the graph, return an empty list.
graph: a dictionary where each key is a node and each value is a list of neighboring nodesstart: the node where traversal beginsExample 1
Input: graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}, start = 'A'
Output: ['A', 'B', 'D', 'C']
DFS explores A -> B -> D before backtracking to visit C.
Example 2
Input: graph = {1: [2, 3], 2: [4], 3: [], 4: []}, start = 2
Output: [2, 4]
Traversal starts at node 2, so only nodes reachable from 2 are visited.
0 <= len(graph) <= 10^52 * 10^5