BFS & DFS

Eunjin Kim·2022년 4월 28일

목록 보기

2/2

너비 우선 탐색(BFS)

루트를 시작으로 탐색을 시작하면 먼저 루트의 자식을 차례로 방문한다. 다음으로 루트 자식의 자식, 즉 루트에서 두 개의 간선을 거쳐 도달할 수 있는 정점을 방문한다.

큐(queue) 자료구조를 사용. 노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보만 큐에 넣어 먼저 큐에 들어있던 노드부터 방문하면 된다.(물론 큐를 사용하지 않아도 구현이 가능)
파이썬에서 큐를 list 타입을 사용해 자료를 입력할 때는 list.append(something), 출력할 때는 list.pop(0) 와 같이 구현하는 경우가 있는데 list.pop(0) 은 시간복잡도가 O(N) 이라 이렇게 구현하면 시간적으로 매우 비효율적인 코드가 만들어지게 된다.
따라서 collections 라이브러리의 deque 를 사용하면 시간을 절약할 수 있다. 또한 인접 노드 중 방문하지 않았던 노드를 큐에 넣을 때는 파이썬 데이터 타입 중 set 을 사용하면 아주 쉽게 구현할 수 있다.

만약 다음과 같이 방향이 있는 유향그래프를 BFS로 탐색한다면,

graph_list = {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_node = 1

from collections import deque

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

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited
  
print(BFS_with_adj_list(graph_list, root_node))

깊이 우선 탐색(DFS)

루트의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳까지 내려가고, 더 못 내려가면 위로 되돌아 오다가 내려갈 곳이 있으면 즉각 내려간다.

스택(stack) 자료구조를 사용. 먼저 방문한 노드에 연결된 노드보다 현재 방문한 노드에 연결된 노드를 방문해야 한 방향으로 갈 수 있다.

만약 이전과 같이 방향이 있는 유향그래프를 DFS로 탐색한다면,

def DFS_with_adj_list(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(DFS_with_adj_list(graph_list, root_node))