[Python] BFS/DFS (Breadth-First Search, Depth-First Search) 구현

1. 그래프의 표현

그래프를 표현할 때는 해당 노드가 어떤 노드와 이어져 있는지를 저장한다.

인접 행렬을 이용해 노드의 관계를 나타내면 메모리의 낭비가 크기 때문에 보통 이어져 있는 노드들의 관계만을 나타내는 방법을 사용한다.

# dict를 이용한 그래프 표현
table = {1: [2, 3, 8],
         2: [1, 7],
         3: [1, 4, 5],
         4: [3, 5],
         5: [3, 4],
         6: [7],
         7: [2, 6, 8],
         8: [1, 7]}
         
         
# 리스트를 이용한 그래프 표현
table2 = [[2, 3, 8],
          [1, 7],
          [1, 4, 5],
          [3, 5],
          [3, 4],
          [7],
          [2, 6, 8],
          [1, 7]]

생성을 할 때는 아래와 같은 방법으로 생성해줄 수 있다.

# dict
table = {i + 1: [] for i in range(n + 1)}

# list
table2 = [[] for _ in range(n + 1)]

2. BFS

BFS는 queue를 이용한 탐색방법이다. 인접한 노드들을 우선적으로 탐색하는 방법이다.

2, 3, 8을 탐색

아직 탐색하지 않은 노드인 7을 탐색

3과 연결된 노드인 4와 5를 탐색

7과 연결된 노드인 6을 탐색

 

bfs를 사용할 때는 큐를 사용하게 된다.

탐색할 노드들을 큐에 순서대로 넣고 deque 연산을 해주면서 연결된 노드들을 탐색하게 된다.

파이썬에서는 deque를 이용해 큐를 구현할 수 있기 때문에 여기서는 deque를 이용해 bfs를 구현해보려 한다.

from collections import deque


def bfs(x):
    q = deque()
    res = []
    q.append(x)
    while q:
        v = q.popleft()
        if v not in res:
            res.append(v)
            for w in table[v]:
                if w not in res:
                    q.append(w)
    return res

3. dfs(Depth-First Search)

dfs는 깊이 우선 탐색으로 인접한 노드들 중 하나를 잡고 계속해서 인접한 노드들을 탐색하는 방법이다.

bfs는 큐를 이용해서 구현할 수 있었다. dfs는 재귀 또는 스택을 이용해 구현할 수 있다.

재귀와 스택의 차이점은 탐색하는 순서에 있다.

스택은 마지막에 들어온 노드를 바로 pop하기 때문에 뒤에 있는 노드들부터 탐색을 하게 된다.

재귀는 반복문을 이용해 앞에서부터 노드들을 탐색하기 때문에 앞에 있는 노드들부터 탐색을 하게 된다.

아직 탐색하지 않은 노드인 7을 탐색

import sys

sys.setrecursionlimit(1_000_000)

# stack 사용
def dfs(x):
    stk = [x]
    res = []
    while stk:
        v = stk.pop()
        if v not in res:
            res.append(v)
            for w in table[v]:
                if w not in res:
                    stk.append(w)
    return res

# recursion 사용
def dfs2(res, x):
    res.append(x)
    for v in table[x]:
        if v not in res:
            dfs2(res, v)
    return res

 

 

 

 

 

dfs를 이용하면 재귀호출을 반복해서 하게 된다. 파이썬에서는 기본적으로 1000번의 재귀함수 호출을 할 수 있는데 이 반복횟수를 수정해주어야 recursionerror 없이 dfs를 사용할 수 있다.

보통 sys에 있는 setrecursionlimit의 값을 100만 정도로 바꾸면 recursionerror 없이 dfs를 수행할 수 있다.