[알고리즘] BFS(Breadth-First Search) - 너비 우선 탐색

이번 시간에는 DFS에 이어 또 다른 그래프 탐색 방법인 BFS에 대해 정리해보려고 합니다.

 

BFS 너비 우선 탐색(Breadth-First Search)

 

출처 : https://developer-mac.tistory.com/64

정의 : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

 

보통 두 노드 사이의 최단 경로를 찾고 싶을 때 사용합니다. 큐(Queue)를 사용하여 구현합니다. 이때 주의할 것은 어떤 노드를 방문했었는지 여부를 반드시 검색해야 합니다. 보통 모든 depth를 한 번에 탐색하기 때문에 단순 검색 속도는 DFS보다 빠릅니다. 하지만 노드의 수가 많아지고 깊이가 깊어지면 비효율적이라는 단점이 있습니다.

 

특징을 정리하면

• Queue를 사용하여 구현, 이는 탐색할 정점들을 저장함으로써 저장공간이 많이 필요
• 그래프가 깊지 않고 규모가 작을 때 효율적
• 단순 검색 속도는 DFS보다 빠름
• 너비를 우선 탐색하기 때문에 최단 경로임을 보장

 

🔰 코드(Kotlin)

import java.util.*

val queue : Queue<Int> = LinkedList()
const val nodeSize = 10
val graph = Array(101){Array<Int>(101){0}}
val visits = Array(101){false}

fun main(){
    //그래프 생성
    graph[1][2] = 1
    graph[2][1] = 1
    graph[1][3] = 1
    graph[3][1] = 1
    graph[2][5] = 1
    graph[5][2] = 1

    //BFS 탐색 시작
    bfs(1)
}

fun bfs(x: Int){
    
    var temp =0
    
    //큐에 삽입
    queue.add(x)
    //방문 표시
    visits[x] = true

    while (queue.isNotEmpty()){
        temp = queue.poll()
        print("$temp ")

        //temp와 연결된 모든 노드 queue에 저장
        for(i in 1..nodeSize){
            if(!visits[i] && graph[temp][i] == 1){
                //큐 삽입
                queue.add(i)
                //방문 확인
                visits[i] = true
            }
        }
    }
}

//Print Result => 1 2 3 5