Base code of DFS & BFS

dfs_bfs.py

"""
* DFS(Depth First Search)
    - Used Data Structure: Stack
    - Time Complexity: O(V+E)
    
* BFS(Breadth First Search)
    - Used Data Structure: Queue
    - Time Complexity: O(V+E)
"""
from collections import deque
from typing import Dict, List


__all__ = ['dfs', 'dfs2', 'bfs', 'bfs2', 'bfs3']


def dfs(start_node:str, graph:Dict[str, list]) -> List[str]:
    stack = deque([start_node])
    visited = set()
    visit_orders = list()
    while stack:
        cur_node = stack.pop()
        if cur_node not in visited:
            visited.add(cur_node)
            visit_orders.append(cur_node)
            stack.extend(reversed(graph[cur_node]))
            # If not reversed, dfs would search right node first because of stack(LIFO).
    return visit_orders


def dfs2(start_node:str, graph:Dict[str, list]) -> List[str]:
    stack = deque([start_node])
    visited = set()
    visit_orders = list()
    while stack:
        cur_node = stack.pop()
        if cur_node not in visited:
            visited.add(cur_node)
            visit_orders.append(cur_node)
            nodes = graph[cur_node]
            nodes.sort(reverse=True)
            for node in nodes:
                if node not in visited:
                    stack.append(node)
    return visit_orders


def bfs(start_node:str, graph:Dict[str, list]) -> List[str]:
    queue = deque([start_node])
    visited = set()
    visit_orders = list()
    while queue:
        cur_node = queue.popleft()
        if cur_node not in visited:
            visited.add(cur_node)
            visit_orders.append(cur_node)
            queue.extend(graph[cur_node])
    return visit_orders


def bfs2(start_node:str, graph:Dict[str, list]) -> List[str]:
    queue = deque([start_node])
    visited = set()
    visit_orders = list()
    while queue:
        cur_node = queue.popleft()
        if cur_node not in visited:
            visited.add(cur_node)
            visit_orders.append(cur_node)
            nodes = graph[cur_node]
            nodes.sort()
            for node in nodes:
                if node not in visited:
                    queue.append(node)
    return visit_orders


def bfs3(start_node:str, graph:Dict[str, list]) -> List[str]:
    queue = deque([start_node])
    visited = set([start_node])
    visit_orders = list([start_node])
    while queue:
        cur_node = queue.popleft()
        nodes = graph[cur_node]
        nodes.sort()
        for node in nodes:
            if node not in visited:
                queue.append(node)
                visited.add(node)
                visit_orders.append(node)
    return visit_orders


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(start_node='A', graph=copy.deepcopy(GRAPH))
    print(f'dfs:: {dfs_result}')

    dfs2_result = dfs2(start_node='A', graph=copy.deepcopy(GRAPH))
    print(f'dfs2: {dfs2_result}')

    bfs_result = bfs(start_node='A', graph=copy.deepcopy(GRAPH))
    print(f'bfs:  {bfs_result}')

    bfs2_result = bfs2(start_node='A', graph=copy.deepcopy(GRAPH))
    print(f'bfs2: {bfs2_result}')

    bfs3_result = bfs3(start_node='A', graph=copy.deepcopy(GRAPH))
    print(f'bfs3: {bfs3_result}')