[알고리즘] 그래프 (6) - 위상 정렬(Topological Sort)

 

 

 

 

 

 

🧐 DAG : Directed Acyclic Graph

DAG는 Cycle이 없는 방향 그래프를 의미합니다.

 

방향 그래프 $G$ 에서 Cycle이 없다는 것은, $G$ 에 대한 DFS Tree가 Back Edge를 가지고 있지 않다는 말과 동일합니다.

 

 

👉 증명

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 위상 정렬(Topological Sort)

위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘입니다.

 

위상 정렬은 오직 DAG 에서만 수행될 수 있습니다.

 

 

 

 

위상 정렬에서의 정렬 기준은 다음과 같습니다.

간선 $($ $u$, $v$ $)$ 가 존재할 경우(즉 $u$ 에서 $v$ 로의 edge가 존재할 경우), 

정점 $u$ 는, 정점 $v$ 보다 순서가 앞입니다.

 

 

 

예를 들어 위 그래프에서 위상 정렬을 수행한 결과는 

$5, 3, 1, 2, 4$ 입니다.

 

 

 

 

 

 

위상 정렬은 DFS를 통해 수행될 수 있으며, 다음과 같은 방법으로 수행 가능합니다.

DFS Tree의 각 node $v$ 에 대해, $post(v)$ 를 기준으로 내림차순(Decreasing Order) 정렬하면,
해당 정렬의 결과는 위상 정렬의 결과가 됩니다.

 

 

 

 

 

 

 

또는 Stack을 사용하면 따로 정렬하지 않고도 문제를 해결할 수 있습니다.

DFS를 수행하며 postVisit($v$)를 할 때마다, $v$ 를 Stack에 push 합니다.

이후 DFS가 모두 종료되면 Stack 에서 차례대로 Pop 해주면, 그것이 위상 정렬의 결과가 됩니다.

 

 

 

 

 

 

 

Kahn's Algorithm이라는 BFS를 사용하는 방법도 있습니다.

그래프의 Source(InDegree가 0)들 중 하나를 출력합니다.

이후 해당 Graph에서 출력한 Source를 제거한 뒤, 나머지 Graph에 대하여 같은 과정을 재귀적으로 반복합니다.

이는 그래프에 Vertex가 존재하지 않을 때까지 반복됩니다.

해당 과정은 다음 블로그에서 자세히 설명되어 있습니다.

 

 

 

 

 

 

 

 

 

🧐 예시 문제

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

위 문제를 위상 정렬로 해결할 수 있습니다.

 

 

👉 해답

 

 Stack을 사용하지 않고 PostOrder를 내림차순하여 해결한 풀이

import java.io.BufferedReader
import java.io.InputStreamReader

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


fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))

    val numOfVertexAndEdge = br.readLine().split(" ")

    val vertexCount = numOfVertexAndEdge[0].toInt()
    val edgeCount = numOfVertexAndEdge[1].toInt()


    // Vertex 등록
    val vertexes = mutableListOf<Vertex>()
    for (i in 0 until vertexCount) {
        vertexes.add(Vertex(i + 1))
    }

    val graph = Graph(vertexCount)
    for (i in 0 until edgeCount) {

        val edge = br.readLine().split(" ")
        graph.addEdge(vertexes[edge[0].toInt()-1], vertexes[edge[1].toInt() - 1])
    }

    GraphExplorer().dfsInAllGraph(graph, vertexes)



    vertexes.sortByDescending { it.postOrder }

    vertexes.forEach { print("${it.value} ") }


}

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

class Graph(
    vertexCount: Int,
) {

    val graph: MutableList<MutableList<Vertex>> = mutableListOf()

    init {
        for (i in 0 until vertexCount) {
            graph.add(mutableListOf())
        }
    }

    fun addEdge(
        start: Vertex,
        end: Vertex,
    ) {
        graph[start.value - 1].add(end)
    }
}

class GraphExplorer {

    var counter = 1

    fun dfsInAllGraph(graph: Graph, vertexes: MutableList<Vertex>) {

        vertexes.forEach {
            if(!it.isVisited)  dfs(graph, it)
        }
    }

    private fun dfs(graph: Graph, current: Vertex) {


        preVisit(current)

        current.isVisited = true

        graph.graph[current.value - 1]
            .forEach {
                if (!it.isVisited)  dfs(graph, it)
            }

        postVisit(current)
    }

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

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

 

 

 

 

 

Stack을 사용한 풀이

import java.io.BufferedReader
import java.io.InputStreamReader

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


fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))

    val numOfVertexAndEdge = br.readLine().split(" ")

    val vertexCount = numOfVertexAndEdge[0].toInt()
    val edgeCount = numOfVertexAndEdge[1].toInt()


    // Vertex 등록
    val vertexes = mutableListOf<Vertex>()
    for (i in 0 until vertexCount) {
        vertexes.add(Vertex(i + 1))
    }

    val graph = Graph(vertexCount)
    for (i in 0 until edgeCount) {

        val edge = br.readLine().split(" ")
        graph.addEdge(vertexes[edge[0].toInt()-1], vertexes[edge[1].toInt() - 1])
    }

    val stack = ArrayDeque<Vertex>()
    GraphExplorer().dfsInAllGraph(graph, vertexes, stack)


//    vertexes.sortByDescending { it.postOrder }
//    vertexes.forEach { print("${it.value} ") }

    while (stack.isNotEmpty()) {
        print("${stack.removeLast().value} ")
    }

}

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

class Graph(
    vertexCount: Int,
) {

    val graph: MutableList<MutableList<Vertex>> = mutableListOf()

    init {
        for (i in 0 until vertexCount) {
            graph.add(mutableListOf())
        }
    }

    fun addEdge(
        start: Vertex,
        end: Vertex,
    ) {
        graph[start.value - 1].add(end)
    }
}

class GraphExplorer {

    var counter = 1

    fun dfsInAllGraph(
        graph: Graph,
        vertexes: MutableList<Vertex>,
        stack: ArrayDeque<Vertex>
    ) {

        vertexes.forEach {
            if(!it.isVisited)  dfs(graph, it, stack)
        }
    }

    private fun dfs(
        graph: Graph,
        current: Vertex,
        stack: ArrayDeque<Vertex>
    ) {

        preVisit(current)

        current.isVisited = true

        graph.graph[current.value - 1]
            .forEach {
                if (!it.isVisited)  dfs(graph, it, stack)
            }

        postVisit(current)
        stack.addLast(current)
    }

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

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

 

 

Kahn's Algorithm 사용

import java.io.BufferedReader
import java.io.InputStreamReader

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


fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))

    val numOfVertexAndEdge = br.readLine().split(" ")

    val vertexCount = numOfVertexAndEdge[0].toInt()
    val edgeCount = numOfVertexAndEdge[1].toInt()


    // Vertex 등록
    val vertexes = mutableListOf<Vertex>()
    for (i in 0 until vertexCount) {
        vertexes.add(Vertex(i + 1))
    }

    val graph = Graph(vertexCount)
    for (i in 0 until edgeCount) {

        val edge = br.readLine().split(" ")
        graph.addEdge(vertexes[edge[0].toInt()-1], vertexes[edge[1].toInt() - 1])
    }

    val stack = ArrayDeque<Vertex>()
    
    GraphExplorer().topologySortByQueue(graph, vertexes)

}

class Vertex(
    val value: Int,
    var isVisited: Boolean = false,
    var inDegree: Int = 0,
)

class Graph(
    vertexCount: Int,
) {

    val graph: MutableList<MutableList<Vertex>> = mutableListOf()

    init {
        for (i in 0 until vertexCount) {
            graph.add(mutableListOf())
        }
    }

    fun addEdge(
        start: Vertex,
        end: Vertex,
    ) {
        graph[start.value - 1].add(end)
        end.inDegree ++
    }
}

class GraphExplorer {


    fun topologySortByQueue(
        graph: Graph,
        vertexes: MutableList<Vertex>,
    ) {

        val queue = ArrayDeque<Vertex>()
        val vertexCount = graph.graph.size
        for (i in 0 until vertexCount) {
            if (vertexes[i].inDegree == 0) queue.addLast(vertexes[i])
        }

        for (i in 0 until vertexCount) {
            
            // 정점을 모두 방문하기 전에 큐가 빈다면 사이클이 발생한 것
            if (queue.isEmpty()){ 
                println("CYCLE!!")
                return
            }

            val vertex = queue.removeFirst()
            print("${vertex.value} ")

            for (i in 0 until graph.graph[vertex.value - 1].size) {
                val vertex1 = graph.graph[vertex.value - 1][i]
                if(--vertex1.inDegree == 0) {
                    queue.addLast(vertex1)
                }
            }
        }
    }
}