그래프 (2) - DAG, 위상 정렬, DAG의 최단 경로

DAG

방향 비순환 그래프(Directed Acyclic Graph, DAG)란 방향 그래프 중 cycle이 없는 그래프를 뜻한다. cycle이 없기 때문에 linearlization이 가능하다. 이렇게 우선순위에 맞게, 즉 화살표가 오른쪽으로만 향하게끔 정점들을 정렬하는 것을 위상 정렬(Topological sort)이라 한다. 위상 정렬의 해답은 여러 개일 수 있다.

 

출처: https://baeseongsu.github.io/posts/algorithms-ch06/

 

DAG는 전체 대상 중 두 대상 간의 관계가 여러 차례 제시된 경우 성립할 수 있다.

ex) 두 학생의 키를 비교하거나, 두 과목 간의 위계가 제시된 경우

이때 위상 정렬 알고리즘을 통해 제시된 관계들을 만족시키는 전체 대상들의 순서를 구할 수 있다.

 

 

DFS를 이용한 위상 정렬

위상 정렬의 구현 방법으로는 대표적으로 2가지가 제시되어 있다.

첫 번째는 앞서 다룬 dfs를 이용하는 것이다. 그래프가 DAG라는 전제 하에, 임의의 정점에서 dfs를 수행하여 도달 가능한 모든 정점은 해당 정점보다 오른쪽에 있어야 한다. 따라서 단순하게 아직 방문하지 않은 정점들에 대해 dfs를 수행하여, 도달한 마지막 정점부터 차곡차곡 스택이나 큐에 넣어주면 된다.

def topo_sort():
    stack = []
    visited = [False]*(N+1)

    def _dfs(u):
        visited[u] = True
        for v in adj[u]:
            if visited[v]: continue
            _dfs(v)
        stack.append(u)
        return

    for i in range(1, N+1):
        if visited[i]: continue
        _dfs(i)
    
    return stack[::-1]

 

 

Kahn's Algorithm

Kahn's Algorith을 이용해서도 위상 정렬이 가능하다.

먼저 알고리즘을 이해하기 위해 노드의 차수(degree)에 대해 간단히 설명한다. degree란 특정 정점에 연결되어 있는 간선의 개수이다. 이때 방향 그래프의 경우 해당 노드로 들어가는 방향의 degree를 incoming degree, 해당 노드에서 나오는 방향의 degree를 outcoming degree라 한다.

​

Kahn's Algorithm에서는 incoming degree를 활용한다. 정렬된 DAG에서 왼쪽 정점부터 하나씩 제거해 나간다고 했을 때, 가장 왼쪽의 정점(시작점)보다 위계가 더 높은 정점은 존재하지 않으므로 항상 incoming degree = 0임을 이용한다.

따라서 각 정점의 incoming degree를 미리 저장해 놓고, incoming degree = 0인 정점을 큐에 저장한다. 이후 하나씩 pop하면서 해당 정점과 연결된 정점들의 incoming degree를 1씩 감소시킨다. 만약 감소시킨 incoming degree가 0이 되는 정점이 있다면 그 정점을 큐에 추가한다.

adj = defaultdict(list)
in_degree = [0]*(N+1)
for _ in range(K):
    x, y = map(int, input().split())
    adj[x].append(y)
    in_degree[y] += 1

def topo_sort():
    q = deque()
    for i in range(1, N+1):
        if in_degree[i] == 0: q.appendleft(i)
    
    res = []
    visited = [False]*(N+1)
    while q:
        u = q.pop()
        visited[u] = True
        res.append(u)
        for v in adj[u]:
            if visited[v]: continue
            in_degree[v] -= 1
            if in_degree[v] == 0: q.appendleft(v)
        
    return res

 

 

DAG의 최단 경로

DAG는 위상 정렬하여 간선에 가중치가 있는 최단 경로 문제를 간단하게 해결할 수 있다. 임의의 정점 $V$의 조상을 $P_1, P_2, \cdots , P_n$이라 하고, 각 조상과 연결된 가중치를 $w_1, w_2, \cdots , w_n$이라 할 때 다음이 성립한다.

 

$$dist[V]=\min(dist[P_1]+w_1, dist[P_2]+w_2, \cdots, dist[P_n]+w_n)$$

 

따라서 전형적인 dp 문제이다. top-down 방식으로 풀기 위해 각 정점에 대한 cost를 담는 list(나 dict)를 만들고, DAG를 위상 정렬한 후 반복문을 돌리면서 연결된 정점의 cost를 계산해 현재의 cost보다 더 작은 경우 갱신하면 된다. 이때 첫 번째 정점의 cost=0으로 설정해 준다.

node_sorted = topo_sort()
cost = [float('inf')]*(N+1)
cost[node_sorted[0]] = 0
while node_sorted:
    u = node_sorted.popleft()
    for v in adj[u]:
        if (new_cost := cost[u] + e[u][v]) < cost[v]:
            cost[v] = new_cost

 

위상 정렬의 시간복잡도는 인접 리스트의 경우 $O(V+E)$, 인접 행렬의 경우 $O(V^2)$이다. DAG의 최단 경로 알고리즘의 시간복잡도는 위상 정렬의 시간복잡도를 따라간다.