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.
Write a function graph_traversals(graph, start) where:
graph is a dictionary mapping each node to a list of its neighborsstart is the node where traversal begins"bfs": list of nodes visited in BFS order"dfs": list of nodes visited in DFS preorderIf start is not in the graph, return { "bfs": [], "dfs": [] }.
Traverse neighbors in the order they appear in the adjacency list.
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.
0 <= len(graph) <= 10^42 * 10^4