[파이썬/python] DFS와 BFS

깊이 우선 탐색 DFS와 너비 우선 탐색 BFS는 그래프를 탐색하는 대표적인 방법이다.

그래프란 정점 node와 정점을 연결하는 간선 edge로 이루어져 있는 자료구조이다.

 

깊이 우선 탐색 DFS

DFS는 Depth First Search의 약자로, 루트 노드에서 시작하여 아래 방향으로 탐색한다.

최대한 깊이 내려간 뒤 더이상 갈 곳이 없을 경우 옆으로 이동하여 탐색하는 방법이기 때문에

루트노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다. 

모든 노드를 방문하고자 하는 경우 유용하며, BFS보다 좀 더 간단하지만 검색속도는 느리다.

자기 자신을 호출하는 재귀적 알고리즘의 형태로 구현하며 스택을 이용한다.

 

 

너비 우선 탐색 BFS

BFS는 Breadth First Search의 약자로, 루트 노드에서 시작하여 오른쪽 방향으로 탐색한다.

최대한 오른쪽으로 간 뒤 더이상 갈 곳이 없을 경우 밑으로 이동하여 탐색하는 방법이기 때문에

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하게 된다.

최단 경로를 찾을 경우 유용하며, DFS보다 검색속도가 빠르지만 좀 더 복잡하다.

재귀적으로 동작하지 않으며 큐를 이용하여 선입선출(FIFO)의 방식으로 탐색한다. 

 

 

파이썬으로 구현하기

구현할 때 어떤 노드를 방문했었는지 방문 여부를 반드시 검사해야한다.

검사하지 않을 경우 무한루프에 빠질 위험이 있다.

DFS와 BFS의 차이는 인접한 노드의 인접한 노드를 먼저 보느냐, 현재 인접한 노드를 모두 보고 넘어가느냐의 차이다.

인접한 노드의 인접한 노드를 먼저 본다면, 가장 최근에 쌓인 순서대로 봐야하므로 stack을 활용하고

현재 인접한 노드를 모두 보고 넘어간다면, 먼저 들어온 것을 먼저 봐야하므로 queue를 활용하면 된다.

 

graph_list = {1: [3, 4],
              2: [3, 4, 5],
              3: [1, 5],
              4: [1],
              5: [2, 6],
              6: [3, 5]}
root_node = 1

딕셔너리 형태의 graph_list에는 key가 갈 수 있는 곳, 즉 인접한 노드들을 value로 저장해두었다.

 

DFS 구현하기

def DFS(graph, root):
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack.extend(sorted(graph[n], reverse=True))
    return visited

print(DFS(graph_list, root_node))

방문한 노드 경로를 저장할 visted와 인접한 노드 중 방문하지 않았던 노드를 저장할 stack를 생성한다.

 

방문 예정인 stack에 값이 있을 동안 반복한다.

가장 첫번째로 방문할 노드 stack.pop()을 n에 저장한다.

n을 방문한 적이 없다면 visited에 추가하여 방문했음을 표시하고

stack에 n과 인접한 노드 graph[n]을 추가하는데,

내림차순으로 정렬하여 추가해야 pop()했을 때 처음 노드부터 방문할 수 있다.

 

 

 

BFS 구현하기

from collections import deque

def BFS(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue.extend(graph[n])
    return visited
  
print(BFS(graph_list, root_node))

방문한 노드 경로를 저장할 visted와 인접한 노드 중 방문하지 않았던 노드를 저장할 queue를 생성한다.

이때 popleft()를 사용하기 위해 queue를 collections의 deque로 생성한다.

 

방문 예정인 queue에 값이 있을 동안 반복한다.

가장 첫번째로 방문할 노드 queue.popleft()를 n에 저장한다.

n을 방문한 적이 없다면 visited에 추가하여 방문했음을 표시하고

queue에 n과 인접한 노드 graph[n]을 추가한다.