BFS

 

 

 BFS?

 BFS란 그래프 탐색의 일종이다. 그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것인데, BFS는 너비 우선 탐색으로 Breadth First Search의 약어이다. BFS는 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 깊이 우선 방식이었던 DFS와는 반대되는 개념인 것이다. 

 

특징

 재귀적인 방식과 스택을 이용한 방식으로 크게 총 2가지로 구현이 가능한 DFS와는 달리, BFS는 재귀적으로 동작하지 않는다. BFS 같은 경우에는 현재 인접한 노드 먼저 방문해야 한다. 다시 말해, 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. 이때 사용되는 자료구조가 큐이다. 

 

구현 방식

1. 루트 노드를 큐에 넣는다.
2. 현재 큐의 노드를 빼서 visited(방문한 노드를 담는다) 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2부터 반복한다.
5. 큐가 비어있다면 탐색을 종료한다.

구현

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}

def bfs_queue(start):
    visited = [start]
    q = deque([start])

    while q:
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    return visited