위상정렬

정의

- DAG(-Directed Acyclic Graph 순환하지 않는 유향 그래프)를 방향성에 거스르지 않도록 순서대로 배열하는 방법.

 

 

예를 들어 

대학을 졸업하고, 이후에 일어나는 일들을 그래프로 표현한다 가정해보자.

부분적인 순서 관계만 있는 상황에서, 필수조건을 만족하면서 치킨집을 운영한다.

 

 kahn 알고리즘 (진입차수를 이용한) 방법

 

* 진입차수 - 특정 노드로 들어오는 간선의 수

진출차수 - 특정 노드에서 나가는 간선의 수

 

- 여러가지 순서가 나올 수 있다.
- 위상정렬의 가능 여부, 가능하다면 어떤 순으로?
- 시간복잡도 O(V+E), 모든 정점에 연결된 간선의 갯수 만큼 반복

 

Queue를 이용하여 구현.
1. 진입차수 degree 0 인 정점을 Queue에 삽입한다.

- 진입차수 Array 및 위상정렬 결과를 담을 리스트, Queue 생성

2. Queue에 꺼내어 그 노드에 연결된 모든 edge를 제거한다.

- 

3. edge를 제거하고, degree 0인 node가 있다면, 큐에 삽입합니다.
4. 2-3을 반복하며, 

   모든 노드 방문전 queue가 빈다면, cycle이 존재하고,
   모든 노드를 방문했다면, 위상정렬된 순서를 생성한다

 

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

2252번: 줄 세우기

 

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

var n = 0
var m = 0

lateinit var adjList: Array<MutableList<Int>>
lateinit var inDegree: IntArray

var isCycle = false
val orderList = mutableListOf<Int>()

fun topologySort() {
	
    val queue: Queue<Int> = LinkedList()

    // 들어오는 degree 0 인 정점을 큐에 삽입
    for (i in 1 until inDegree.size) {
        if (inDegree[i] == 0) queue.add(i)
    }

    for (i in 1 until inDegree.size) {
    	// 큐가 다 비워졌다면 사이클이 존재
        if (queue.isEmpty()) {
            isCycle = true
            return
        }
        // queue에서 꺼내어 연결된 모든 edge를 제거한다.
        val node = queue.poll()
        orderList.add(node)
        for (next in adjList[node]) {
            // inDegree 1개 줄이는것은 곳 제거하는것.
            inDegree[next] -= 1
            // degree 0인 node가 있다면, 큐에 삽입
            if (inDegree[next] == 0) {
                queue.add(next)
            }
        }
    }
}

fun main() = with(System.`in`.bufferedReader()) {

    val info = readLine().split(" ").map { it.toInt() }
    n = info[0]
    m = info[1]

    adjList = Array(n + 1) { mutableListOf() }
    inDegree = IntArray(n + 1)
    for (i in 0 until m) {
        val edge = readLine().split(" ").map { it.toInt() }
        // u -> v 
        val u = edge[1]
        val v = edge[0]
        adjList[u].add(v)
        // 진입차수 카운팅.
        inDegree[v] += 1
    }

    topologySort()
    val sb = StringBuilder()
    orderList.reversed().forEach {
        sb.append("$it ")
    }

    println(sb.toString())
    return@with Unit
}

DFS 를 이용한 방법 

-  상대적으로 위 방법에 비해서 구현이 복잡하다.

 

Stack을 이용한 구현.

1. 임의 노드를 선정

2. dfs 탐색을 하며 진출차수가 0인 노드에서 멈춤 (정렬상 마지막 노드)

3. 탐색의 역순으로 노드를 스택에 담고, 그래프에서 지운다.

 

새로운 임의 노드를 골라 반복한다.

이후, 그래프의 모든 노드가 담기면 스택에서 나오는 순서가 위상정렬 순서다