[알고리즘] BFS 너비 우선 탐색 : 필수 기본 정리 : 과정, Kotlin 구현예제

목차

 

저번 포스트에서 그래프를 통해 object 사이에 관계를 살펴보았습니다. 그래프는 정점으로 object를 나타내고, 변으로 object의 관계를 나타냈습니다. 그래프에 대하여 자세히 알고 싶으시다면 이전 포스트를 참고해주세요. 

[알고리즘] Graph 그래프 : 필수 기본 정리 - 가중치, 방향, 무방향 그래프, 인접리스트, 인접행렬

 

BFS탐색 알고리즘

이런 그래프탐색을 위한 알고리즘이 존재하는데 그중 하나가 BFS 너비우선탐색 알고리즘입니다. BFS는 정점(vertex)의 너비를 우선으로 하여 접근하며 탐색합니다. 

 

BFS를 사용하여 다양한 문제를 풀수있습니다. 

1. 최소신장 트리 Minimum-spanning-tree

2. 정점사이 path 찾기

3. 정점 사이 가장 짧은 거리 구하기

 

BFS는 아무 정점을 선택하여 그 정점과 연결된 다른 정점들을 찾아봅니다. 그리고 근접한 정점들을 접근 후, 자식 노드들에 접근하게 됩니다. 자세한 과정을 살펴보겠습니다. 

 

BFS원리

 

 

BFS 구현

BFS 구현

 

fun breadthFirstSearch(source: Vertex<T>): Arraylist<Vertex<T>>{
	val queue= QueueStack<Vertex<T>>
    val enqueue = ArrayList<Vertex<T>>
    val visited = ArrayList<Vertex<T>>()
    
    //more to come
    
    return visited
}

위 3가지 벨류의 역할을 설명해보겠습니다. 

1. Queue : 이웃 자식이 어떤 것인지 탐색하고 다음으로 찾아야 할 자식을 알아둡니다. 

2. Enqueued :  어떤 정점이 enqueue 되었는지 확인합니다 그럼으로써 같은 정점을 추가하는 걸 방지합니다. 

3. Visited : 어떤 정점이 접근되었는지 확인합니다. 

 

queue.enqueue(source) //1
enqueued.add(source)

while (true) {
    val vertex = enqueue.dequeue() ? : break//2
    
    visited.add(vertex) //3
    
    val neighborEdges = edges(vertex) //4
    neighborEdges.forEach{
    
      if(!enqueued.contains(it.destination)) { //5
          queue.enqueue(it.destination)
          enqueue.add(it.destination)
      } 
    }
}

위 코드를 설명해보겠습니다. 

1. BFS 알고리즘을 source 정점(vertex)을 enqueue 하면서 시작합니다. 

2. 큐가 빌 때까지 정점을 dequeue를 진행합니다.

3. 정점을 dequeue 할 때마다, 새로 접근한 정점들을 큐에 추가합니다. 

4. 모든 변들을 찾기 시작합니다. 그리고 반복문으로 각 변마다 아래 오퍼레이션을 반복합니다. 

5. 각 변들을 체크하면서, 도착한 정점이 queue에 추가된 적이 있는지 확인하고 아니면 추가합니다. 

 

메인 문에서 위 함수를 실행해보겠습니다. 

val vertices = graph.breadthFirstSearch(a)
	vertics.forEach{
    	println(it.data)
}

위 코드를 실행 시 결과입니다. 

A
B
C
D
E
F
G
H

 

BFS 알고리즘 분석

BFS에서 enqueue를 사용하기 때문에 이 작업을 할 때 걸리는 속도는 O(V)입니다. 모든 변을 접근할 때는 O(E). 그러므로 BFS의 전체적인 속도는 O(V+E)입니다.