BFS, DFS

2021-03-10

다음과 같은 방향성을 지닌 그래프를 탐색한다 치자.

graph = {1: set([3, 4]),
         2: set([3, 4, 5]),
         3: set([1, 5]),
         4: set([1]),
         5: set([2, 6]),
         6: set([3, 5])}
root = 1

너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)을 하는 방법을 각각 알아보자.

BFS(Breadth First Search, 너비 우선 탐색)

너비 우선 탐색은 시작점인 루트 노드와 같은 거리에 있는 노드를 우선 방문하는 탐색법이다. queue 자료 구조를 이용한다. collection 라이브러리의 deque 함수를 사용하는 것이 시간복잡도를 줄이는 방법이다.

BFS

BFS 함수 코드는 아래와 같다.

from collections import deque

def BFS(graph, root):
    visited = [] # 방문한 노드는 리스트로 모은다 
    queue = deque([root]) # 루트 노드를 리스트로

    while queue: # queue 리스트 요소가 없어질 때까지 반복
        n = queue.popleft() # 가장 앞 요소를 꺼낸다
        if n not in visited:
            visited.append(n) # 방문하지 않은 노드라면 방문 리스트에 추가
            queue += graph[n] - set(visited) # 방문하지 않은 노드로 가서 방문한 루트를 뺀 나머지 노드를 queue 맨 앞에 넣어준다. 여기부터 다시 탐색.
    return visited
  
print(BFS(graph, root))
DFS(Depth First Search, 깊이 우선 탐색)

깊이 우선 탐색은 시작 노드에서 최대한 깊이까지 내려갈 수 있는 루트를 탐색하는 방법이다. BFS의 queue 대신 stack 자료 구조를 이용한다. stack은 말하자면 list 자료 구조다.

DFS

DFS 함수 코드는 아래와 같다.

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

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited

print(BFS(graph, root))

[참고한 글]