Problem

At Notion, graph traversal is used to explore dependency graphs and connected components. Given a graph as an adjacency list and a starting node, implement both Breadth-First Search (BFS) and Depth-First Search (DFS) and return the order in which nodes are visited.

Formal Specification

Write a function graph_traversals(graph, start) where:

• graph is a dictionary mapping each node to a list of its neighbors
• start is the node where traversal begins
• Return a dictionary with two keys:
  • "bfs": list of nodes visited in BFS order
  • "dfs": list of nodes visited in DFS preorder

If start is not in the graph, return { "bfs": [], "dfs": [] }.

Traverse neighbors in the order they appear in the adjacency list.

Examples

Example 1 Input: graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}, start = "A" Output: {"bfs": ["A", "B", "C", "D", "E"], "dfs": ["A", "B", "D", "C", "E"]} Explanation: BFS explores level by level, while DFS goes as deep as possible before backtracking.

Example 2 Input: graph = {1: [2, 3], 2: [4], 3: [], 4: []}, start = 2 Output: {"bfs": [2, 4], "dfs": [2, 4]} Explanation: Starting from node 2, only nodes reachable from 2 are visited.

Constraints

• 0 <= len(graph) <= 10^4
• Total number of edges is at most 2 * 10^4
• Graph may contain cycles
• Node values are hashable