[그래프탐색] BFS - JS, Python

너비 우선 탐색 - Breath Frist Search

• 가까운 노드부터 탐색하는 알고리즘
• DFS는 최대한 멀리있는 노드를 우선으로 탐색하는 방식으로 동작한다했는데, BFS는 가까이 있는 노드부터 우선탐색
• 큐를 이용한 선입선출방식
• 가중치 없는 그래프에서 최단 경로 문제에서 많이 쓰인다
  • ex) 서울에서 부산으로 가는데 거쳐야하는 최소 정거장의 수
  • ex) 임의의 4자리 숫자 x에서 한자리(0~9)로 변경하면 다른 숫자 y를 만들 수 있음 이떄 x에서 z를 만들기 위한 최소 변경횟수
  • ex) 친구관계에서의 단계 
  

1. 탐색 시작 노드를 큐에 삽입하고 방문처리

2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리

3. 2번 과정을 더이상 수행할 수 없을 때까지 반복

BIG O

• 모든 노드에서 for문 수행
• 노드의 관점에서 보지말고 edge의 관점에서 볼것
• 인접리스트 구현 : O(|V| + |E|) (V는 정점의 수, E는 간선의 수)
• 인접 행렬 구현 : O(|V| ^ 2) (V는 정점의 수, E는 간선의 수)

dfs와 비교하고 싶으면 참고하세요!

2021.05.02 - [이론/알고리즘] - [그래프탐색] DFS- JS, Python

 

BFS의 장점

• 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작(최소경로)
• 단순 검색 속도가 깊이 우선탐색(DFS)보다 빠름 (파이썬에선 deque사용하면 O(N)의 검색시간)
• 너비를 우선탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다
• 최단 경로가 존재하면 경로가 무한히 깊어진다해도 최잔 경로를 찾을 수 있다

BFS의 단점

• 재귀 호출의 DFS와는 달리 큐 다음에 탐색할 정점들을 저장해야하므로 메모리가 많이 듦
• 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적

코드구현

Python

from collections import deque

def bfs(graph, start, visited):
    # 큐 구현을 위해 deque라이브러리 사용
    queue = deque([start])
    visited[start] = True
    # 큐가 빌때까지 반복
    while queue:
        v = queue.popleft() 
        print(v, end=' ') # 1 2 3 8 7 4 5 6
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                # print(queue)


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

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

bfs(graph, 1, visited)

JS

const bfs = function(graph, v, visited) {
    let queue = []
    visited[v] = true
    queue.push(v)
    while (!(queue.length === 0)) {
        v = queue.shift()
        console.log(v) // 1 2 3 8 7 4 5 6
        for (const a of graph[v]) {
            if (visited[a] !== true) {
                visited[a] = true
                queue.push(a)
            } 
        }
    }
    
}

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

let visited = Array(9).fill(false)
bfs(graph, 1, visited)