그래프 - 너비 우선 탐색 (BFS, Breadth-First Search)

#1 그래프의 탐색

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

그래프의 각 정점을 한번씩 방문할 필요가 있다고 해보자. 그 방문의 방법에는 크게 2가지 방법이 있다. 하나는 너비 우선 탐색이다. 또 다른 하나는 깊이 우선 탐색이다. 본 게시글에서는 너비 우선 탐색법을 다룬다. (깊이 우선 탐색에 대해서는 이 게시글에서 다룬다)
 

#2 알고리즘

https://commons.wikimedia.org/wiki/File:Breadth-first-tree.svg

원래라면 순서도를 통해 알고리즘을 소개하고 코드로 넘어가는 편이 이해하기 좋지만, 그래프 탐색 알고리즘은 그냥 코드부터 보는 게 오히려 이해가 더 빠르다고 생각한다. 다만, 인접 배열 (Adjacency Array)의 지식에 대해서는 알고 있어야 한다는 전제 하다. 여기서 사용할 인접 배열은 이 게시글에 있다 (가중치가 없는 무향 그래프).

대신 왜 '너비 우선' 탐색이라는 이름이 붙었는지는 설명할 가치가 있다. 너비 우선 탐색은 다른 말로 '내 자식 우선' 탐색이다. 일반적으로 그래프는 깊이의 높낮이가 위 그래프처럼 y축과 평행하게 그려진다. 따라서 내 자식을 우선으로 탐색한다는 말은, (2 → 3 → 4) → (5 → 6 → 7 → 8) → ...와 같은 식으로 탐색한다는 말이 된다 (같은 괄호 내의 정점들은 서로 순서가 뒤바뀔 수도 있음 (#3 참조)). 이 탐색은 x축(너비)를 우선해 이동하는 모양이 된다 (y축 이동은 x축 탐색이 종료된 후에 시행된다. 우선순위가 아닌 것이다). 그래서 너비 우선 탐색이라 부른다.
 

#3 코드 - 코틀린

#3-1 기본 코드

import java.util.*

fun main() {
    // (1) listOfAdjacencyArray[n]이 가지는 의미를 알아야 한다 (설명 참조)
    val listOfAdjacencyArray = listOf(
        arrayOf(1, 2),
        arrayOf(0, 3, 4),
        arrayOf(0, 4),
        arrayOf(1),
        arrayOf(1, 2)
    )

    bfs(listOfAdjacencyArray, 0)  // 0번 정점(vertex)에서 탐색 시작
}

fun bfs(listOfAdjacencyArray: List<Array<Int>>, startVertex: Int) {
    // (2) Queue로 탐색 순서를 결정한다. discovered는 Queue에 이미 있거나, 방문이 완료된 정점들을 기록하는 Set(집합)이다
    val queue: Queue<Int> = LinkedList()
    val discovered = mutableSetOf<Int>()

    // (3) startVertex부터 Queue에 넣는다. 동시에 discovered에도 추가한다.
    queue.add(startVertex)
    discovered.add(startVertex)

    while (queue.isNotEmpty()) {
        // (4) 정점을 Queue에서 빼내고, 방문해서 진행할 일을 수행한다. 여기선 doSomethingFunction()으로 표현했다
        val vertex = queue.remove()
//      doSomethingFunction(vertex)
        println("Visit complete: $vertex")

        // (5) (4)에서 빼냈던(remove()) 정점의 이웃 정점마다 (6)을 수행
        for (neighborVertex in listOfAdjacencyArray[vertex]) {
            // (6) discovered 목록에 없다면, Queue에 추가하고 동시에 discovered에도 추가한다
            if (neighborVertex !in discovered) {
                queue.add(neighborVertex)
                discovered.add(neighborVertex)
            }
        }
    }
}

(1) listOfAdjacencyArray[n]이 가지는 의미를 알아야 한다
정점에 부여된 번호가 0 ~ N일 때, listOfAdjacencyArray[n]은 n번 정점에 연결된 이웃(neighbor) 정점들의 배열을 의미한다.

(2) Queue로 탐색 순서를 결정한다. discovered는 ...
Queue로 탐색 순서를 결정한다는 말은, Queue에 add된 순서대로 방문한다는 이야기가 된다.

(3) startVertex부터 Queue에 넣는다. 동시에 discovered에도 추가한다.
시작 정점을 Queue와 discovered 각각에 추가한다.

(4) 정점을 Queue에서 빼내고, 방문...
queue.remove()되어 doSomethingFunction()이 수행되는 시점부터 '해당 정점에 방문했다'고 볼 수 있다. 관점에 따라, discovered에 목록이 추가되는 순간에 정점에 방문했다고 볼 수도 있겠으나, 만약 그 관점이라면 doSomethingFunction()의 위치를 discovered.add() 직후로 이동시켜야 할 것이다. 이 경우의 코드는 #3-3에 있다.

(5) (4)에서 빼냈던(remove()) 정점의 이웃 정점마다 (6)을 수행
listOfAdjacencyArray[n]은 방금 방문 완료한 정점 n에 연결된 이웃 정점들의 배열이다. 이 배열의 요소마다 (6)을 수행한다.

(6) discovered 목록에 없다면, Queue에 추가하고 동시에 discovered에도 추가한다
배열 listOfAdjacencyArray[vertex]의 각 요소를 Queue에 넣는다. #2의 내용 중 (2 → 3 → 4) → (5 → 6 → 7 → 8) → ...에서 괄호 안의 순서는 바뀔 수 있다고 한 이유가 이 때문이다. 만약 #2의 그래프의 인접 배열을 만들 때 listOfAdjacencyArray[1] = { 3, 4, 2 }로 두었다면 (3 → 4 → 2) → ...순으로 Queue에 들어갈 것이고, listOfAdjacencyArray[1] = { 4, 2, 3 }로 두었다면 (4 → 2 → 3) → ...순으로 Queue에 들어갈 것이다. 그리고 Queue는 선입선출이므로, 당연히 방문 순서 또한 똑같이 따라갈 것이다.
 

#3-2 제네릭을 이용한 코드

import java.util.*
import kotlin.collections.HashMap

fun main() {
    // (1) mapOfAdjacencyArray[n]이 가지는 의미를 알아야 한다 (설명 참조)
    val mapOfAdjacencyArray = HashMap<String, Array<String>>()
    mapOfAdjacencyArray["강아지"] = arrayOf("고양이", "사슴")
    mapOfAdjacencyArray["고양이"] = arrayOf("강아지", "코뿔소", "흰머리오목눈이")
    mapOfAdjacencyArray["사슴"] = arrayOf("강아지", "흰머리오목눈이")
    mapOfAdjacencyArray["코뿔소"] = arrayOf("고양이")
    mapOfAdjacencyArray["흰머리오목눈이"] = arrayOf("고양이", "사슴")

    bfs(mapOfAdjacencyArray, "강아지")  // "강아지" 정점(vertex)에서 탐색 시작
}

fun <T> bfs(mapOfAdjacencyArray: Map<T, Array<T>>, startVertex: T) {
    // (2) Queue로 탐색 순서를 결정한다. discovered는 Queue에 이미 있거나, 방문이 완료된 정점들을 기록하는 Set(집합)이다
    val queue: Queue<T> = LinkedList()
    val discovered = mutableSetOf<T>()

    // (3) startVertex부터 Queue에 넣는다. 동시에 discovered에도 추가한다.
    queue.add(startVertex)
    discovered.add(startVertex)

    while (queue.isNotEmpty()) {
        // (4) 정점을 Queue에서 빼내고, 방문해서 진행할 일을 수행한다. 여기선 doSomethingFunction()으로 표현했다
        val vertex = queue.remove()
//      doSomethingFunction(vertex)
        println("Visit complete: $vertex")

        // (5) (4)에서 빼낸 정점의 이웃 정점마다 (6)을 수행
        for (neighborVertex in mapOfAdjacencyArray[vertex]!!) {
            // (6) discovered 목록에 없다면, Queue에 추가하고 동시에 discovered에도 추가한다
            if (neighborVertex !in discovered) {
                queue.add(neighborVertex)
                discovered.add(neighborVertex)
            }
        }
    }
}

지금까지 정점을 편의상 Int형이라고만 다뤘지만, 정점을 구분하는 기준이 다른 데이터형일 수도 있다. 그 경우에 사용할 수 있도록 제네릭을 이용해 리팩토링한 코드다. listOfAdjacencyArray가 mapOfAdjacencyArray로 바뀐 것에도 주목하자. listOfAdjacencyArray의 index는 반드시 Int여야 한다는 제약 조건이 있기에 이 index의 역할을, mapOfAdjacencyArray의 key가 수행하게 만들었다.

 

#3-3 doSomethingFunction() 위치 변경

import java.util.*

fun main() {
    // (1) mapOfAdjacencyArray[n]이 가지는 의미를 알아야 한다 (설명 참조)
    val mapOfAdjacencyArray = HashMap<String, Array<String>>()
    mapOfAdjacencyArray["강아지"] = arrayOf("고양이", "사슴")
    mapOfAdjacencyArray["고양이"] = arrayOf("강아지", "코뿔소", "흰머리오목눈이")
    mapOfAdjacencyArray["사슴"] = arrayOf("강아지", "흰머리오목눈이")
    mapOfAdjacencyArray["코뿔소"] = arrayOf("고양이")
    mapOfAdjacencyArray["흰머리오목눈이"] = arrayOf("고양이", "사슴")

    bfs(mapOfAdjacencyArray, "강아지")  // "강아지" 정점(vertex)에서 탐색 시작
}

fun <T> bfs(mapOfAdjacencyArray: Map<T, Array<T>>, startVertex: T) {
    // (2) Queue로 탐색 순서를 결정한다. visited는 Queue에 이미 있거나, 방문이 완료된 정점들을 기록하는 Set(집합)이다
    val queue: Queue<T> = LinkedList()
    val visited = mutableSetOf<T>()

    // (3) startVertex부터 Queue에 넣는다. visited에도 추가함과 동시에 방문해서 진행할 일을 수행한다. 여기선 doSomethingFunction()으로 표현했다
    queue.add(startVertex)
    visited.add(startVertex)
//  doSomethingFunction(startVertex)
    println("Visit complete: $startVertex")

    while (queue.isNotEmpty()) {
        // (4) 정점을 Queue에서 제거한다
        val vertex = queue.remove()

        // (5) (4)에서 빼낸 정점의 이웃 정점마다 (6)을 수행
        for (neighborVertex in mapOfAdjacencyArray[vertex]!!) {
            // (6) visited 목록에 없다면, Queue에 넣고 visited에도 추가함과 동시에 방문해서 진행할 일을 수행한다. 여기선 doSomethingFunction()으로 표현했다
            if (neighborVertex !in visited) {
                queue.add(neighborVertex)
                visited.add(neighborVertex)
//              doSomethingFunction(neighborVertex)
                println("Visit complete: $neighborVertex")
            }
        }
    }
}

Queue에서 빼낼 때가 아니라, 등록할 때 노드를 방문한 것으로 취급하면 doSomethingFunction()을 위와 같은 코드로 변경할 수도 있다. 이 경우 (노드를 발견) == (노드를 방문)이므로, Set의 이름도 #3-1에서 사용한 이름인 discovered가 아닌 visited로 변경했다.

 

#4 요약

너비 우선 탐색은 인접 배열의 원소들을 Queue에 넣는다.