깊이 우선 탐색 (DFS)와 넓이 우선 탐색 (BFS)

graph = [
    [],
    [2, 3, 4],
    [1, 5, 6],
    [1],
    [1, 7],
    [2, 8],
    [2, 8],
    [4],
    [5, 6]
]

1. DFS (Depth-First Search)

1) 재귀함수로 구현

visited = []

def dfs_recursion(graph, node, visited):
    visited.append(node)
     
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursion(graph, neighbor, visited)
    return visited

dfs_recursion(graph, 1, visited) # [1, 2, 5, 6, 3, 4, 7, 8]

2) stack으로 구현

def dfs_stack(graph, node):
    stack = [node]
    visited = [node]

    while stack:
        current_node = None
        for node in graph[stack[-1]]:
            if node not in visited:
                current_node = node
                break

        if current_node == None:
            stack.pop()
        else:
            visited.append(current_node)
            stack.append(current_node)

    return visited

2. BFS (Breadth-First Search)

queue로 구현

from collections import deque

def bfs_queue(graph, node):
    visited = [node]
    deq = deque()
    
    deq.append(node)
    
    while deq:
        cur_node = deq.popleft()
       
        for neighbor in graph[cur_node]:
            if neighbor not in visited:
                visited.append(neighbor)
                deq.append(neighbor)
                
    
    return visited # [1, 2, 3, 4, 5, 6, 7, 8]