[자료구조] Python BFS, DFS

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

BFS란 그래프 탐색에 사용하는 기법입니다.
너비 우선 탐색이라고 불리며 너비를 우선시하여 그래프를 탐색하는 기법 입니다. 시작점에서 같은 거리의 있는 노드를 우선 탐색하는 기법입니다.

BFS

BFS 알고리즘은 큐(queue) 자료구조를 사용합니다. 노드를 방문하면서 인접한 노드 중 방문 하지 않던 노드만 큐에 넣어 큐에 있떤 노드부터 방문하는 방법입니다.

파이썬에서 큐는 list를 이용하여 만들 수 있지만 list.pop(0)은 시간복잡도가 O(N) 이므로 비효율적인 코드가 됩니다.

때문에 python 에서는 collections 라이브러리의 deque를 이용하여 시간복잡도를 줄입니다.

또한 방문하지 않은 노드를 큐에 넣을때 집합(set)을 이용하면 쉽게 구현할 수 있습니다.

다음 그래프를 탐색한다고 했을때

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(Depth First Search, 깊이 우선 탐색)

DFS는 BFS와는 다르게 갈 수 있는 만큼 가장 깊은 곳부터 탐색하는 것으로 이전 갈림길에서 선택하지 않았던 노드를 방문 하는 방법입니다.

DFS

DFS는 스택(stack)자료구조로 만들어집니다

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

방문한 노드를 담는 visited list를 만듭니다

stack은 탐색을 시작할 노드로 초기화 해줍니다.

 

while이 실행하면 stack에 담겨있는 값이 없을때까지 반복합니다

n에 방문할 노드를 담아주고 만약 그 노드가 방문한 노드가 아니라면 방문 처리(visited.append(n)를 해줍니다

스택에는 연결된 노드중 간 노드는 제외한 값을 다시 넣어줍니다

이후 visited list에 들어간 순서는 노드가 지나간 순서로 출력되므로 DFS가 나옵니다