BFS

import java.util.LinkedList
import java.util.Queue

fun main() {
    val graph = arrayOf(
        intArrayOf(),
        intArrayOf(2,3,8),
        intArrayOf(1,7),
        intArrayOf(1,4,5),
        intArrayOf(3,5),
        intArrayOf(3,4),
        intArrayOf(7),
        intArrayOf(2,6,8),
        intArrayOf(1,7)
    )

    val visited = BooleanArray(graph.size){ false }

    bfs(graph, 1, visited)
}

fun bfs(graph: Array<IntArray>, node: Int, visited: BooleanArray) {
    val queue: Queue<Int> = LinkedList()
    queue.add(node)
    visited[node] = true

    while(queue.isNotEmpty()) {
        val currentNode = queue.remove()
        print("$currentNode ")

        for (nextNode in graph[currentNode]) {
            if (!visited[nextNode]) {
                queue.add(nextNode)
                visited[nextNode] = true
            }
        }
    }
}

큐 자료구조에 기초한다. 탐색 수행에 O(N) 시간이 소요된다.