[알고리즘] 그래프 (2) - DFS

 

 

 

 

 

 

 

 

 

🧐 DFS (Depth-First Search) - 깊이우선탐색

이전 글에서 살펴본 explore procedure를 이용하여 그래프 상의 모든 정점을 한번씩 방문하는 방법인 DFS 알고리즘에 대해 알아보도록 하겠습니다.

 

 

네 알아봤습니다 :)

 

 

 

 

 

 

코드로 구현

 

 

다음 그래프에 대한 dfs를 코드로 구현해 보도록 하겠습니다.

 

/**
 * Created by ShinD on 2022/09/22.
 */

fun main() {

    val graph = GraphMaker().make()

    GraphExplorer().dfs(graph)

    GraphMaker.vertexSet().forEach {
        println("END [${it.value}], [ ${it.preOrder}, ${it.postOrder} ]")
    }
}

class Graph(
    val vertexSet: Set<Vertex>,
    val graph: List<List<Vertex>>,
)

class GraphMaker {

    companion object {

        val a = Vertex('a')
        val b = Vertex('b')
        val c = Vertex('c')
        val d = Vertex('d')
        val e = Vertex('e')
        val f = Vertex('f')
        val g = Vertex('g')
        val h = Vertex('h')
        val i = Vertex('i')
        val j = Vertex('j')
        val k = Vertex('k')
        val l = Vertex('l')

        fun vertexSet(): Set<Vertex> {
            return setOf(
                a, b, c, d, e, f, g, h, i, j, k, l
            )
        }
    }

    fun make(): Graph {
        return Graph(
            vertexSet = vertexSet(),
            graph = listOf(
                listOf(b, e),           // a
                listOf(a),              // b
                listOf(d, g, h),        // c
                listOf(c, h),           // d
                listOf(a, i, j),        // e
                listOf(),               // f
                listOf(c, h, k),        // g
                listOf(c, d, g, k ,l),  // h
                listOf(e, j),           // i
                listOf(e, i),           // j
                listOf(g, h),           // k
                listOf(h),              // l
            )
        )
    }
}

class Vertex(
    val value: Char,
    var preOrder: Int = 0,
    var postOrder: Int = 0,
    var isVisited: Boolean = false,
) {

    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (other !is Vertex) return false

        if (preOrder != other.preOrder) return false
        if (postOrder != other.postOrder) return false
        if (value != other.value) return false

        return true
    }

    override fun hashCode(): Int {
        var result = preOrder
        result = 31 * result + postOrder
        result = 31 * result + value.hashCode()
        return result
    }
}

class GraphExplorer {

    // 시작 전 1로 초기화
    private var counter = 1

    private fun visited(vertex: Vertex) {
        vertex.isVisited = true
        println("VISIT [${vertex.value}]")
    }

    private fun preVisit(vertex: Vertex) {
        vertex.preOrder = counter
        counter++
    }

    private fun postVisit(vertex: Vertex) {
        vertex.postOrder = counter
        counter++
    }

    fun explore(
        graph: Graph,
        root: Vertex,
    ) {

        val idx = root.value - 'a'

        // 방문 처리
        visited(root);

        // preVisit
        preVisit(root);

        // 루트 vertex와 adjacent 한 모든 vertex 탐색
        graph.graph[idx].forEach { vertex ->
            /// 아직 방문하지 않았다면 explore
            if (!vertex.isVisited) explore(graph, vertex)
        }

        // postVisit
        postVisit(root);
    }

    fun dfs(
        graph: Graph,
    ) {

        // 모든 Vertex에 대해서 visited를 false로 초기화
        graph.vertexSet.forEach { it.isVisited = false }

        // 모든 Vertex를 방문할 때까지 반복한다.
        graph.vertexSet.forEach {
            // 방문하지 않은 Vertex 하나에서 explore 실행
            if (!it.isVisited) explore(graph, it)
        }
    }
}

 

 

결과는 다음과 같습니다.

 

 

 

 

 

 

 

 

 

조금 위에서 알아보았듯이 explore procedure 과정을 DFS tree로 나타낼 수 있습니다.

 

 

따라서 explore 과정을 반복하는 DFS 알고리즘의 경우에도

전체 과정을 DFS tree들의 서로소 합집합(disjoint union), 즉 forest로 표현 가능합니다.

 

 

 

이때 DFS forest를 이루는 각각의 DFS tree는 그래프 상에서 Connected Component에 대응합니다.

 

Connected Component가 뭐냐구요?

 

 

다음 글에서 알아보도록 하겠습니다.