Implement DFS and BFS

EasyPython

Problem

Zemoso Technologies models service dependencies and workflow transitions as a directed graph. Given an adjacency-list representation and a starting service, return the nodes reachable from that service in both depth-first search and breadth-first search order.

Implement both traversals in one function. A node must appear at most once in each result, and when multiple unvisited neighbors are available, process them in the order listed in the adjacency list. The DFS result must use iterative depth-first search, so it does not depend on Python recursion depth.

Formal Specification

Input: graph, a dictionary mapping each string node to a list of neighboring string nodes, and start, a string contained in graph.
Output: A dictionary with keys "dfs" and "bfs". Each value is a list of node names in the corresponding traversal order.
Traversals include only nodes reachable from start.
The graph may contain cycles and self-loops.

Constraints

1 <= number of nodes <= 10^5
0 <= number of edges <= 2 * 10^5
Node names are unique, non-empty strings
Every listed neighbor is a key in graph
start is a key in graph

Function Signature

def traverse_graph(graph, start):

Formal Specification

Input: graph, a dictionary mapping each string node to a list of neighboring string nodes, and start, a string contained in graph.
Output: A dictionary with keys "dfs" and "bfs". Each value is a list of node names in the corresponding traversal order.
Traversals include only nodes reachable from start.
The graph may contain cycles and self-loops.