[Python] 파이썬으로 DFS와 BFS 구현하기

DFS와 BFS

• DFS와 BFS는 그래프의 탐색 방법
• 목적: 한 정점에서 시작하여 연결되어 있는 모든 정점을 1번씩 방문

 

DFS

• 한 우물을 깊이 파면서 탐색 
• 재귀함수 혹은 스택으로 구현 가능

d_check = [False for _ in range(n + 1)]
def dfs(x):
    d_check[x] = True
    print(x, end = ' ')
    for y in edge[x]:
        if d_check[y] == False:
            dfs(y)

 

BFS

• 여러 우물을 동시에 같은 깊이로 탐색
• 최단 경로 찾기에 사용

from collections import deque

def bfs():
    queue = deque([start])
    b_check = [False for _ in range(n + 1)]
    b_check[start] = True
    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in edge[v]:
            if not b_check[i]:
                b_check[i] = True
                queue.append(i)

 

예제 문제

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력. 단, 방문할 수 있는 정점이 여러 개면 정점 번호가 작은 것 먼저 방문

 

입력

첫째 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V가 주어짐.

다음 M개의 줄어네는 간선이 연결하는 두 정점의 번호가 주어짐.

 

from collections import deque
import sys

n, m, start = map(int, sys.stdin.readline().strip().split())

edge = [[] for _ in range(n + 1)]

for _ in range(m):
    v1, v2 = map(int, sys.stdin.readline().strip().split())
    edge[v1].append(v2)
    edge[v2].append(v1)

for e in edge:
    e.sort()

d_check = [False for _ in range(n + 1)]
def dfs(x):
    d_check[x] = True
    print(x, end = ' ')
    for y in edge[x]:
        if d_check[y] == False:
            dfs(y)

def bfs():
    queue = deque([start])
    b_check = [False for _ in range(n + 1)]
    b_check[start] = True
    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in edge[v]:
            if not b_check[i]:
                b_check[i] = True
                queue.append(i)

dfs(start)
print()
bfs()
print()