[파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색)

BFS란?

 

BFS(Breadth First Search)는 DFS와 마찬가지로 그래프의 모든 노드를 탐색하는 방법 중 하나로, 너비를 우선으로 탐색한 후 인접한 노드부터 탐색하는 알고리즘입니다. 스택 자료구조를 활용하는 DFS와 달리 BFS에서는 일반적으로 큐 자료구조를 이용합니다.

 

DFS 배우기 --> 2022.07.12 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

[파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

 

그래프 배우기 --> 2022.07.04 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 그래프(Graph)

[파이썬으로 배우는 자료구조] 그래프(Graph)

 

큐 자료구조 배우기 --> 2022.06.29 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue)

[파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue)

 

---

BFS 알고리즘의 탐색 과정 및 구현 방법

 

 위와 같은 그래프로 1번 노드부터 큐 자료구조에 넣고, BFS 알고리즘을 적용하여 탐색을 해보겠습니다. 연결된 노드가 여러 개일 때는 오름차순으로 큐 자료구조에 삽입하도록 하겠습니다.

 

1) 1번 노드를 큐에서 제거해주고, 방문처리합니다. 1번 노드와 인접하면서 방문하지 않은 노드는 2, 4, 5번 노드입니다. 따라서 2, 4, 5번 노드를 순서대로 큐에 삽입합니다.

 

2) 2번 노드를 큐에서 제거해주고, 방문처리합니다. 2번 노드와 인접하면서 방문하지 않은 노드는 6번 노드입니다. 따라서 6번 노드를 큐에 삽입합니다.

 

3) 4번 노드를 큐에서 제거해주고, 방문처리합니다. 4번 노드와 인접하면서 방문하지 않은 노드는 3, 7번 노드입니다. 따라서 3, 7번 노드를 순서대로 큐에 삽입합니다.

 

4) 5번 노드를 큐에서 제거해주고, 방문처리합니다. 5번 노드와 인접하면서 방문하지 않은 노드는 8번 노드입니다. 따라서 8번 노드를 큐에 삽입합니다.

 

5) 6번 노드를 큐에서 제거해주고, 방문처리합니다. 6번 노드와 인접하면서 방문하지 않은 노드는 없습니다.

 

6) 3번 노드를 큐에서 제거해주고, 방문처리합니다. 3번 노드와 인접하면서 방문하지 않은 노드는 없습니다.

 

7) 7번 노드를 큐에서 제거해주고, 방문처리합니다. 7번 노드와 인접하면서 방문하지 않은 노드는 없습니다.

 

8) 8번 노드를 큐에서 제거해주고, 방문처리합니다. 8번 노드와 인접하면서 방문하지 않은 노드는 없습니다.

 

9) 큐가 비게 되어 탐색이 종료됩니다.

 

탐색 순서: 1 -> 2 -> 4 -> 5 -> 6 -> 3 -> 7 -> 8

 

---

BFS 알고리즘의 특징

 

BFS 알고리즘은 DFS 알고리즘과 달리 재귀적으로 동작하지 않고, 시작 노드로부터의 거리에 따라 단계별로 탐색을 한다는 특징을 갖고 있습니다.

따라서 노드를 차례로 저장한 후에 꺼낼 수 있는 FIFO 방식의 큐 자료구조를 사용합니다. 경로가 무한히 깊어져도 최단 경로를 반드시 찾을 수 있으며 노드 수가 비교적 적고, 깊이가 얕은 해가 존재할 때 유리하게 사용됩니다.

 

하지만 DFS 알고리즘과 달리 큐를 이용하여 다음 탐색할 노드들을 저장하기 때문에 더 큰 저장공간이 필요합니다.

 

시간 복잡도

인접행렬 - O(|V|^2) (|V|개의 노드에 대해서 |V|개의 엣지를 모두 탐색해야 함)

인접 리스트 - O(|V|+|E|) (|V|개의 노드와 총 |E|개의 엣지 탐색)

---

BFS 알고리즘 구현

코드

from collections import deque

# BFS함수
def BFS(graph, start, visited):
    # 큐 자료구조 deque로
    queue = deque([start])   

    # 빈 큐가 될 때 까지
    while queue:
        v = queue.popleft()
        # 해당 노드 방문처리
        visited[v] = True
        print(v, end=' ')
        # 해당 노드와 연결되어 있고, 방문하지 않은 노드들 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)

if __name__ == "__main__":
    graph = [
        [],
        [2, 4, 5],
        [1, 6],
        [4],
        [1, 3, 7],
        [1, 8],
        [2],
        [4],
        [5]
    ] 

    # 방문 리스트
    visited = [False] * 9

    # 맨 처음 1번 노드부터
    BFS(graph, 1, visited)

실행 결과