AAAt 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^4graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}, start = "A"Output{"bfs": ["A", "B", "C", "D", "E"], "dfs": ["A", "B", "D", "C", "E"]}WhyBFS visits nodes by distance from A, while DFS follows B to D before backtracking to C and E.graph = {1: [2, 3], 2: [4], 3: [], 4: []}, start = 2Output{"bfs": [2, 4], "dfs": [2, 4]}WhyOnly nodes reachable from 2 are included, and both traversals visit 4 after 2.graph = {1: [2], 2: [3], 3: [1]}, start = 1Output{"bfs": [1, 2, 3], "dfs": [1, 2, 3]}WhyThe visited set prevents infinite loops even though the graph contains a cycle.0 <= len(graph) <= 10^40 <= total number of edges <= 2 * 10^4Graph may be directed and may contain cyclesNode values are hashableNeighbors should be visited in the order they appear in each adjacency listdef graph_traversals(graph, start):
