10 - BFS

BFS(Breath-First Search), 너비우선 탐색 방식

 

1. BFS란?

 

너비 우선 탐색(Breadth-first search, BFS)는 맹목적 탐색 방법 중 하나로 시작 정점(vertex)을 방문한 후 인접한 모든 정점들을 우선으로 방문하는 방법이다.

 

더 이상 방문하지 않은 정점이 없을 때 까지 방문하지 않은 정점들에 대해서도 너비 우선 탐색을 적용하고, 일반적으로 queue 자료 구조를 이용해서 순차적으로 접근이 가능하도록 구현이 가능하다.

 

Tree상에서 BFS로 탐색을 진행하는 경우에는 cycle이 생기는 경우가 없지만, graph에 BFS를 적용하는 경우에는 cycle이 있을 수 있기 때문에 무한 루프에 빠지는 것을 방지하기 위해서 방문 표시를 하면서 탐색을 진행해야 한다.

 

2. BFS 간단한 구현 방법

 

아래의 그림의 케이스를 예로 들겠다. '0' vertex에서 graph의 탐색을 시작한다고 가정하겠다. 그렇다면 '0'의 인접 vertex인 '1', '3' vertex를 반문하게 될 것이다.

 

이때, 인접한 vertex인 '1', '3'을 방문한 이후에는 다시 '1', '3'의 인접 vertex를 방문하게 될 탠데, 이때 이전에 방문한 vertex에 대한 방문 여부를 기록하지 않는다면, '3'의 인접한 vertex인 '0'을 다시 방문하고 '1'은 또 '3'과 다시 인접한 vertex이기 때문에 방문하게 되는 흐름에 빠져서 무한 루프를 돌게 될것이다.

 

따라서 방문한 vertex에 대한 방문 여부를 기록하면서 그래프 탐색을 진행해야 한다.

 

또 '0' vertex에서 탐색을 시작해서 순차적으로 인접한 vertex를 방문하도록 구현하기 위해서 queue 자료 구조를 이용해야 한다.

* queue https://jyu-seo.tistory.com/15

06 - Stack & Queue

 

 

4. BFS 소스코드

앞선 개념을 바탕으로 간단하게 cpp 언어를 이용해 BFS를 구현하면 아래와 같이 구현할수 있다.

from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 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 함수 호출
bfs(graph, 1, visited)

#실행결과 : 1, 2, 3, 8, 7, 4, 5, 6