BFS (Breadth First Search )

# 정의

너비우선탐색이라 불리는 BFS 알고리즘은 굉장히 잘 알려져있고 컴퓨터 관련 전공생들은 거의 모두 알고 있는 알고리즘이다. chatGPT에 따른 BFS의 정의는 다음과 같다.

BFS(Breadth-First Search) 알고리즘은 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다. 이 알고리즘은 너비 우선 탐색을 하며, 시작 노드에서 가까운 노드들부터 우선적으로 방문합니다.

BFS를 이해하기 위해선 "그래프"라는 것이 무엇인지부터 알아야한다.

 

# Graph

그래프(Graph)는 데이터를 저장하고 관리하는 자료구조 중 하나로, 객체들 간의 관계를 나타내는 추상적인 자료구조입니다. 그래프는 노드(Node)와 간선(Edge)로 이루어져 있습니다.

노드는 그래프에서 하나의 객체를 나타내며, 간선은 이 객체들 간의 관계를 나타냅니다.
간선은 노드와 노드 사이에 존재하며, 방향성 여부에 따라 방향 그래프와 무방향 그래프로 구분됩니다.

그래프는 다음과 같은 특징을 가집니다.
1. 노드(Node): 그래프에서 하나의 객체를 나타냅니다.
2. 간선(Edge): 그래프에서 노드와 노드 사이의 관계를 나타냅니다.
3. 방향성(Directedness): 간선의 방향성에 따라 방향 그래프와 무방향 그래프로 구분됩니다.
4. 가중치(Weight): 간선의 가중치가 존재할 수 있습니다.
5. 사이클(Cycle): 그래프에서 자기 자신으로 되돌아올 수 있는 경로를 사이클이라고 합니다.
6. 연결성(Connectivity): 그래프에서 노드들이 서로 얼마나 연결되어 있는지를 나타냅니다.

 

# Code

이제 개념을 장착했으니 BFS가 어떤 방식으로 코드상에서 진행되는지 알아보자

1. 시작 노드를 큐(queue)에 추가합니다.
2. 큐에서 노드를 하나씩 꺼내면서 해당 노드의 인접한 노드들을 큐에 추가합니다. 이때, 이미 방문한 노드는 큐에 추가하지 않습니다.
3. 큐가 빌 때까지 2번 과정을 반복합니다.

 

가장 기본적인 BFS 파이썬 코드이다.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()

        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)

    return visited

# BFS 수행시간

BFS 알고리즘은 일반적으로 인접 리스트(Adjacency List) 형태의 자료구조를 사용할 때 O(V+E)의 수행시간을 가지지만, 인접 행렬(Adjacency Matrix) 형태의 자료구조를 사용할 때 O(V^2)의 수행시간을 가지게 됩니다.

( 빅오표기법으론 DFS와 똑같지만 그래프의 형태, 목적에 따라 차이가 남 )

# BFS의 기능

그렇다면 "가장 가까운 노드부터 탐색한다"라는 행위로 우리는 어떤것을 얻을 수 있을까?

1. 그래프 탐색
2. 최단 경로 찾기 (단, 이 경우 가중치가 없어야하며 만약 있다면 Dijkstra 알고리즘으로 가능)
3. 트리의 레벨 순회(Level Order Traversal)
4. 그래프의 컴포넌트 개수 구하기

 

# BFS 실생활 사례

이에 더 나아가서 이러한 기능들을 실생활에서 어떻게 적용중일까?

1. 소셜 네트워크에서 특정 사용자와 직접적으로 연결된 사용자들을 찾거나, 인터넷에서 특정 웹페이지와 연결된 다른 웹페이지들을 찾을 때
2. 게임에서 AI가 최단 경로를 찾거나, 특정 아이템을 찾기 위해 맵을 탐색할 때 
3. 지도 서비스 지도 서비스에서 특정 위치와 연결된 위치들을 찾을 때
4. 암호 해독

 

# Reference

ChatGPT