DFS with recursive

dfs_recursive.py

__all__ = ['dfs_recursive']


visited = set()
visited_orders = list()


def dfs_recursive(start_node: str, graph: dict[str, list[str]]) -> None:
    if start_node in visited:
        return
    
    visited.add(start_node)
    visited_orders.append(start_node)
    adj_nodes = graph[start_node]
    for node in adj_nodes:
        dfs_recursive(node, graph)
        

if __name__ == '__main__':
    import copy
    
    
    GRAPH_INFO = r"""
    [Graph]
                    A
                  /   \
                 B     C
                / \   / \
               D   E F   G
              /|\       / \
             H I J     K   L
            /\
           M  N
           
    * DFS Result: ["A", "B", "D", "H", "M", "N", "I", "J", "E", "C", "F", "G", "K", "L"]
    * BFS Result: ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"]
    """
    GRAPH = {
        "A": ["B", "C"],
        "B": ["A", "D", "E"],
        "C": ["A", "F", "G"],
        "D": ["B", "H", "I", "J"],
        "E": ["B"],
        "F": ["C"],
        "G": ["C", "K", "L"],
        "H": ["D", "M", "N"],
        "I": ["D"],
        "J": ["D"],
        "K": ["G"],
        "L": ["G"],
        "M": ["H"],
        "N": ["H"],
    }
    print(GRAPH_INFO)

    dfs_result = dfs_recursive(start_node="A", graph=copy.deepcopy(GRAPH))
    print(f"dfs: {visited_orders}")