넓이 우선 탐색 알고리즘(Breadth-First Search Algorithm)

BFS

BFS 알고리즘은 ‘너비 우선 탐색’이라는 의미를 가진다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다.
DFS가 최대한 멀리 있는 노드부터 우선적으로 탐색한다면, BFS는 그와 반대로 가까운 노드부터 탐색을 진행한다.
DFS가 스택 구조를 활용했다면, BFS는 선입선출 방식인 큐 자료구조를 이용한다.
인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면, 자연스럽게 먼저 들어온 것이 먼저 나가게 되고 가까운 노드부터 탐색을 진행하게 된다.
BFS 알고리즘의 동작 방식은 다음과 같다.

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

위 그래프로 깊이 우선 탐색을 한다면 코드는 아래와 같이 작성할 수 있다.

---

파이썬 코드

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start]) #큐에 시작노드 넣기
    visited[start] = True #방문한 노드 목록에 시작노드 넣기
    while queue:  #queue가 있는 동안...?
        v = queue.popleft() #v는 queue에서 popleft()한 원소, 방문했으니 큐에서 제거
        print(v, end = '') #방문한 노드 출력
        for i in graph[v]: #그래프에서 v번째 원소의 i번째 원소(노드)에서
            if not visited[i]: #방문한 노드에 i번째 원소(노드)가 없다면...
                queue.append(i) #큐에 i번째 원소(노드)를 추가한다.
                visited[i] = True #방문한 노드는 True처리

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9 #방문한 노드 초기화

bfs(graph, 1, visited) 

---

C언어 코드