Edmond's algorithm (Directed-MST)

먼저 (undirected) MST에 대해 생각해보자. 무향 그래프 $G=(V, E,w)$를 생각하자. ($|V|=N, |E|=M, w:E\to \mathbb{R}$)

Spanning Tree란 $G$에서 $N-1$개의 간선을 택해 만든 트리 $T=(V, E'), E'\subseteq E$를 말한다. 이 트리의 가중치는 $w(T)=\sum_{e\in E}{w(e)}$이다. $G$의 spanning tree 중 가중치가 가장 작은 것을 minimum spanning tree(MST)라 한다. MST는 Prim's algorithm 혹은 Kruskal's algorithm을 이용하면 $O(MlogN)$으로 해결할 수 있다. $O(M \alpha (M, N))$인 알고리즘도 존재하지만 PS에서는 잘 쓰이지 않는다.

 

이제 Directed graph에 대해 생각해보자. 유향 그래프 $G=(V, E, w)$가 있다. $r \in V$를 루트로 하는 spanning tree $T$는 간선이 부모 $\to$ 자식 방향으로 존재한다. $r$을 루트로 하는 spanning tree가 존재하기 위해서는 $r$에서 모든 정점으로 가는 경로가 존재해야 한다.

DMST를 구하는 알고리즘을 유도하기 위해서는 몇 가지 Lemma들이 필요하다. 아래 내용은 www.cs.tau.ac.il/~zwick/grad-algo-13/directed-mst.pdf를 요약한 것이다.

 

Lemma 1.1

$T$가 $G$의 spanning tree rooted at $r$이라는 것은 아래와 동치이다.

: $T$에서 $r$의 indegree는 0이고,  $r$을 제외한 정점들의 indegree는 1이고, 사이클이 없다.

 

Corollary 1.2

$T$가 $G$의 spanning tree rooted at $r$이라 하자. $T$에 속하지 않는 $(u, v) \in E$에 대해 $v$가 $u$의 조상이 아니라면, $T \cup \{ (u, v) \} \backslash \{ (u', v) \}$ 역시 $G$의 spanning tree rooted at $r$이다. ($(u', v)\in T$는 $v$로 향하는 (유일한) 간선)

 

Lemma 1.1을 생각하며, $r$을 제외한 각 정점들에 대해 그 정점으로 들어가는 간선 중 가중치가 최소인 것을 생각하자. 이러한 간선들을 모두 모았을 때 acyclic 하다면 이것이 DMST이다. cycle $C$가 존재한다면 아래와 같은 Lemma가 성립한다.

 

Lemma 4.1

$C$의 간선 중 하나를 제외한 나머지를 모두 포함하는 DMST rooted at $r$이 존재한다. 

 

이제 $C$의 정점들을 하나로 합치고, $C$로 들어가는 간선들의 가중치를 적당히 바꾸자. $C$로 들어가는 간선 $(u, v)$를 생각하자($v \in C$). 간선 $(u', v) \in C$가 존재할 것이다. $(u, v)$의 가중치에서 $(u', v)$의 가중치를 빼준다. 이렇게 만들어진 ($C$가 압축된) 새로운 트리를 $\bar{T}$라 하자. $T$와 $\bar{T}$는 일대일 대응이 된다.

 

Lemma 4.2

$\bar{w}(\bar{T})=w(T)-w(C)$

 

따라서 이렇게 트리를 점점 압축해나가면 DMST를 구현할 수 있다. 아래는 $O(NM)$으로 DMST rooted at $r$(의 가중치)을 구하는 코드이다. 트리가 압축되는 것이 최대 $N$번이고, 압축시키는 과정이 각각 $O(M)$이다.

 

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;

struct EDGE {
	int u, v;		// u->v
	lint c;
	EDGE(int u, int v, lint c): u(u), v(v), c(c) {}
};

lint dmst(int N, vector<EDGE> ed, int r) {
	vector<int> mnu(N), lbl(N);		// mnu: 최소 간선의 정점, lbl: 압축 시 새로운 정점 번호
	vector<lint> mnc(N);			// mnc: 최소 간선의 가중치
	lint ans = 0;
	while(true) {
		fill(mnc.begin(), mnc.end(), LINF);
		for(EDGE e : ed) 				// 최소 간선을 찾아준다
			if(e.u != e.v && e.c < mnc[e.v]) {
				mnc[e.v] = e.c;
				mnu[e.v] = e.u;
			}
		mnc[r] = 0;
		for(int i = 0; i < N; i++) ans += mnc[i];	// 사이클의 가중치를 답에 더해준다

		fill(lbl.begin(), lbl.end(), -1);
		int K = 0;
		lbl[r] = K++;
		for(int i = 0; i < N; i++) if(lbl[i] == -1) {	// 최소간선으로 이루어진 그래프를 살핀다
			int x;
			for(x = i; lbl[x] == -1; x = mnu[x]) lbl[x] = -2;
			if(lbl[x] == -2) {			// 사이클이 발견된 경우
				for(; lbl[x] == -2; x = mnu[x]) lbl[x] = K;
				K++;
			}
			for(x = i; lbl[x] == -2; x = mnu[x]) lbl[x] = K++;
		}

		if(K == N) break;			// 최소 간선들이 트리를 이룬다(=DMST 발견)

		N = K;
		for(EDGE &e : ed) {
			e.c -= mnc[e.v];		// 사이클로 들어가는 간선의 가중치를 바꿔줌
			e.u = lbl[e.u];			// 정점에 새로운 번호를 부여해준다
			e.v = lbl[e.v];
		}
		r = lbl[r];
	}
	return ans;
}

 

 

 

$O(MlogN)$의 시간복잡도로 DMST를 구할 수도 있다고 한다. $k$개의 루트에 대한 DMST를 구하고자 한다면 $O(MlogN+kN)$으로 구할 수 있다. 구현은 복잡하여 생략하고, 여기에서 그 아이디어는 다루고자 한다.

• 그래프 전체가 strongly connected이도록 하자. 가중치가 충분히 큰 간선들을 추가해주면 답을 바꾸지 않으며 strongly connected로 바꾸어줄 수 있다.
• 그래프를 압축할 때 $r$을 특정하지 않는다. 그러면 전체 그래프가 하나의 (압축된)정점으로 바뀌게 된다. $r$을 특정하지 않았기 때문에, 여러 루트에 대한 DMST를 함께 빠르게 구할 수 있다.
• 정점들이 압축되는 과정은 union find로 관리한다.
• 모든 (압축된) 정점들에 대해 그 정점으로 들어오는 간선들을 min-heap으로 관리한다. 사이클을 압축시킬 때는 두 heap을 합쳐주면 된다.
• 각 정점에 대해 '들어오는 간선 중 가중치가 최소인 것'(=최소간선)을 찾는 과정을 생각하자. $v$에 해당되는 최소간선이 $(u, v)$였다면, 그 다음에는 $u$에 대한 최소간선을 찾아준다. 이렇게 순차적으로 $v_1, v_2, ..., v_k$에 대해 최소간선을 찾았다 하자. ($v_i$에 대한 최소간선이 $(v_{i+1}, v_i)$) $v_k$의 최소간선이 $(u, v_k)$라 하자. $u==v_i$라면, $\{ v_i, ..., v_k \}$가 사이클을 이룬다. 그렇지 않다면, $v_{k+1}=u$로 추가해주면 된다.

DMST를 이용하면 아래 문제를 풀 수 있다. ($O(MN)$ 알고리즘으로도 충분)

www.acmicpc.net/problem/16127