[Python] DFS, BFS

def dfs(graph, v, visited):  # graph: 각 노드가 연결된 정보
    visited[v] = True  # 현재 노드 방문 처리
    print(v, end=' ')
    for i in graph[v]:  # 현재 노드(graph[v]와 연결된 노드를 재귀적으로 방문
        if not visited[i]:
            dfs(graph, i, visited)
            
# 참고로, visited의 초기값은 visited=[False]*(n+1)로 초기화를 해주는데, 
# n이 아니라 (n+1)인 이유는 0번 인덱스는 비워두고 사용하지 않기 때문이다.

 

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:  # 큐가 빌 때까지 반복
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# bfs는 인접 노드들을 "한 번에" 큐에 넣는 특징이 있음
# bfs는 간선의 비중이 모두 동일하다는 가정에서 최단 거리 문제에 자주 사용