DFS, BFS Python 구현

1. DFS 구현

DFS는 stack으로 구현되며 재귀 함수를 통해 구현할 수 있다.

import sys
input = sys.stdin.readline

def dfs(now, graph, visited):
    visited[now] = True

    print(now, end=' ')
    
    for next in graph[now]:
        if not visited[next]:
            dfs(next, graph, visited)

n, m, start_node = map(int, input().rstrip().split())                                      
graph = [[] for _ in range(n+1)]                       
visited = [False for _ in range(n+1)]

for _ in range(m):                                  
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(n+1):
    graph[i].sort()
    
dfs(start_node, graph, visited)

2. BFS 구현

BFS는 queue를 통해 구현되며 파이썬에서는 deque를 활용한다. 아래와 같이 구현할 수 있다.

import sys
from collections import deque

input = sys.stdin.readline

def bfs(start, graph, visited):
    visited[start] = True

    queue = deque([start])

    while queue:
        now = queue.popleft();
        print(now, end=' ')

        for next in graph[now]:
            if not visited[next]:
                visited[next] = True
                queue.append(next)
    
n, m, start_node = map(int, input().rstrip().split())                                      
graph = [[] for _ in range(n+1)]                       
visited = [False for _ in range(n+1)]

for _ in range(m):                                  
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(n+1):
    graph[i].sort()

bfs(start_node, graph,visited)