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^5graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}, start = 'A'Output['A', 'B', 'D', 'C']WhyDFS visits A first, then goes as deep as possible through B to D before backtracking to C.graph = {1: [2, 3], 2: [4], 3: [], 4: []}, start = 2Output[2, 4]WhyStarting from 2 only reaches 4, so nodes 1 and 3 are not included.0 <= len(graph) <= 10^50 <= total number of edges <= 2 * 10^5Graph may contain cyclesNodes may be integers or stringsIf start is not in graph, return an empty listdef depth_first_search(graph, start):
