알고리즘 이론 - BFS

BFS

• BFS는 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선 탐색하는 알고리즘임.
• 큐 자료구조 이용
  • 1. 시작 노드를 큐에 삽입하고 방문 처리함(True)
  • 2. 큐에서 노드를 꺼내고, 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
  • 3. 2번이 안될 때까지 반복해서 재귀함.

위 사진과 같이 시작 노드에서 가장 인접한 값 1, 2를 탐색하고 방문처리한다. 그리고 1번 노드를 큐에서 pop하며 1과 인접한 노드들을 방문한다. 그 다음 2를 pop하고 인접한 5, 6노드를 pop한다.

• DFS, BFS는 기본적으로 collections에 내장된 deque를 import해 쓰는게 훨씬 효율적이다.
• BFS는 최단 거리 문제로 자주 출제된다.

from collections import deque


def bfs(graph, start, visited):
    #큐 구현에 적합한 deque 사용
    queue = deque([start]) # 현재 노드 큐에 삽입(방문)

    visited[start] = True #큐에 들어간 후 방문 처리

    while queue:
        #큐에서 원소 출력
        v = queue.popleft()
        print(v, end =' ')
        #아직 방문하지 않은 원소들 queue에 삽입하고 방문 -> 직접 연결되지 않은 노드들까지 모두 방문하기 위함.
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
#각 노드를 False로 방문하지 않았음을 표시
visited = [False] * 9

bfs(graph, 1, visited)