BFS

BFS는 Breadth-First-Search로 너비 우선 탐색 이라고 부릅니다.
쉽게 말하면 가까운 노드부터 탐색하는 알고리즘 입니다.
DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다면, BFS는 그 반대입니다.

1. 동작 방식

BFS 구현에서는 선인선출(First In First Out) 방식인 큐 자료구조를 이용하는 것이 정석입니다.
인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 됩니다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 합니다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

2. 예시

다음과 같이 그래프와 큐가 있다고 가정하겠습니다. 큐의 원소는 위에서 들어오고 아래서 꺼냅니다.

1. 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 합니다.

방문 처리된 노드는 회색으로, 큐에서 꺼내 현재 처리하는 노드는 하늘색으로 표현합니다.

2. 큐에서 '1'을 꺼내고 방문하지 않은 인접 노드 '2','3','8'을 모두 큐에 삽입하고 방문 처리를 합니다.

3. 큐에서 '2'를 꺼내고 방문하지 않은 노드 '7'을 삽입하고 방문 처리를 합니다.

4. 큐에서 노드 '3'을 꺼내고 방문하지 않은 인접 노드 '4'와 '5'를 모두 큐에 삽입하고 방문 처리를 합니다.

5. 큐에서 노드 '8'을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.

6. 큐에서 노드 '7'을 꺼내고 방문하지 않은 인접 노드 '6'을 큐에 삽입하고 방문 처리를 합니다.

7. 남아 있는 노드에 방문 하지 않은 인접 노드가 없습니다. 따라서 모든 노드를 차례대로 꺼내면 최종적으로 다음과 같습니다.

결과적으로 탐색의 순서(큐에 들어간 순서)는 다음과 같습니다. 1 -> 2 -> 3 -> 8 -> 7 -> 4-> 5 -> 6 입니다.
너비 우선 탐색 알고리즘인 BFS는 큐 자료구조에 기초한다는 점에서 구현이 간단합니다.
파이썬에서는 deque 라이브러리를 사용하는 것이 좋고 탐색을 수행함에 있어 O(N)의 시간이 소요됩니다. 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편입니다.

3. 코드

# queue를 구현하기 위한 deque 라이브러리 사용
from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    # 시작 노드로 deque 선언
    queue = deque([start])
    # 현재 노드 방문 처리
    visited[start] = True
    # 큐가 빌때까지 반복
    while queue:
        # 큐에서 하나씩 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=" ")
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# bfs수행(2차원 리스트, 시작 노드, 방문 처리를 확인하기 위한 리스트)
bfs(graph, 1, visited)

4. 정리

다양한 방식으로 구현할 수 있지만 아래의 표와 같이 구현하는 것이 가장 간결한 방식입니다.

참조
이것이 취업을 위한 코딩 테스트다 with 파이썬

틀린 부분은 댓글로 남겨주시면 수정하겠습니다..!!ㄴ