DFS

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)
    )

    var visited = BooleanArray(9){ false }

    dfs(graph, 1, visited)
}

fun dfs(graph: Array<IntArray>, v: Int, visited: BooleanArray) {
    visited[v] = true
    print("$v ")
    for(node in graph[v]) {
        if(!visited[node]) {
            dfs(graph, node, visited)
        }
    }
}

현재 노드를 방문 처리하고, 현재 노드와 연결된 다른 노드를 재귀적으로 방문한다.

 

DFS는 스택 자료구조에 기초한다는 점에서 재귀함수로 구현할 수 있다.

탐색 수행에 있어 데이터 개수가 N개인 경우 O(N)시간이 소요된다.