Problem
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.
Formal Specification
- Input:
graph: a dictionary where each key is a node and each value is a list of neighboring nodesstart: the node where traversal begins
- Output:
- A list containing nodes in DFS visitation order
Constraints
- 0 <= len(graph) <= 10^5
- 0 <= total number of edges <= 2 * 10^5
- Graph may contain cycles
- Nodes may be integers or strings
- If start is not in graph, return an empty list
Function Signature
def depth_first_search(graph, start):
You are practicing as a guest. Sign up free to run your code against the sample data. Your draft stays right here.
