[그래프 탐색] 파이썬으로 구현하는 DFS, BFS

그래프 탐색이란?

그래프의 각 노드를 방문하는 것으로, 크게 깊이 우선탐색(Depth First Search, DFS)과 너비 우선 탐색(Bredth-First Search, BFS) 알고리즘이 있습니다.  DFS는 주로 재귀 혹은 스택으로 구현하게 되며, 백트래킹 문제에서 주로 사용됩니다. BFS의 경우 주로 큐로 구현하며, 최단 경로를 구하는 문제에서 자주 사용됩니다. 

 

파이썬으로 그래프 입력받기

---

그래프 탐색 방법을 구현하기 전, 파이썬에서 그래프를 입력받는 방법에 대해서 알아보도록 하겠습니다. 파이썬에서 제공하는 List, deque등 다양한 자료형으로 저장할 수 있지만, 개인적으로 파이썬의 Dictionary 자료형으로 입력받는 것을 가장 선호해 이 방법을 소개하고자 합니다.

 

앞의 그림과 같이 노드 간 방향이 있는( v -> w ) 방향 그래프(directed graph)일 경우 다음과 같이 dictionary 타입의 G에 저장할 수 있습니다.

G = { 
    1:[2,3,4],
    2:[5],
    3:[5],
    4:[],
    5:[6,7],
    6:[],
    7:[3]
}

 

v->w 방향으로 연결되어있을 때 입력이 다음과 같은 형태로 들어온다고 가정해봅시다.

7 8 #(# of node, # of edge)
1 2 #(1 ->2)
1 3
1 4
...
7 3 #(7 ->3)

 

이 경우, 아래의 코드로 그래프를 저장할 수 있습니다.

*무방향 그래프(undirected graph)일 경우 아래 주석처리한 코드를 추가하면 됩니다.

from collections import defaultdict

N, M = map(int, input().split()) # n: # of node, M : # of edge
G = defaultdict(list)

for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
    # if undirected graph G: u-v, v-u
    # G[v].append(u)

 

파이썬으로 DFS 구현하기

---

반복 형태에 따른 구현

1. 재귀로 구현

2. For문으로 구현하기(스택 사용)

 

DFS는 이름 그대로 그래프의 깊이를 우선으로 방문하게 됩니다. 일반적으로는 스택(stack)을 사용해 For문으로 구현하나 재귀를 이용하면 좀 더 간단한 구현이 가능합니다. 

 

 

1. 재귀로 구현

def dfs(start, visited = [False]*(N+1)):
    visited[start] = True
    for v in G[start]:
        if not visited[v]:
            dfs(v, visited) 
    return visited

먼저 재귀(Recursion)를 이용해서 구현한 코드입니다. 방문한 노드(v)가 아닐 경우 dfs()함수를 호출해 방문하는 코드로, visited에 모든 노드가 들어올때까지 재귀호출을 하는 형태입니다.

 

2. For문으로 구현하기(스택 사용)

from collections import deque

def dfs(start, visited=[False]*(N+1)):
    stack = deque()
    stack.append(start)
    while stack: 
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            for u in G[v]:
                stack.append(u)
    return visited

recursion depth를 고려해야하는 코드라면, 위와 같이 재귀대신 for문을 사용할 수 있습니다. 단, 인접 노드를 차례로 저장하고 이후 최근 방문한 순으로 꺼내쓸 수 있는 자료구조가 필요하므로 선입후출(FILO) 구조인 스택(stack)을 사용하면 됩니다. 파이썬에서는 따로 구현할 필요없이 list를 사용해 스택의 pop, push 연산을 할 수 있습니다. 

 

 

파이썬으로 BFS 구현하기

---

큐로 구현하기

from collections import deque

def bfs(start, visited=[False]*(N+1)):
    que = deque()
    que.append(start)
    while que: 
    	v = que.popleft()
        if not visited[v]:
            visited[v] = True
            for u in G[v]:
                que.append(u)

    return visited

BFS의 경우 그래프의 너비 우선 탐색 방법으로, For문으로 구현할 때 스택을 이용하는 DFS와는 달리 큐(queue)를 이용해 구현합니다. 파이썬에서 제공하는 deque을 이용하면 따로 큐를 구현할 필요없이 BFS를 간단하게 구현할 수 있습니다.