12. 그래프 (2) (최단경로, 프림, 크루스칼)

 

 

최단 경로 (다익스트라)

최단 경로를 찾는 문제는, 한 정점으로부터 다른 모든 정점으로 가는데 걸리는 최단 경로를 통해 결국은 원하는 지점으로 최단경로를 찾는 방법이다. 다익스트라는 여기서 첫 점을 기준으로 정점들을 추가하며 거리를 갱신시킨다.

D(z)를 x에서 z까지의 최단 경로라 한다면
$D(z) = Min(D(z) , D(y) + c(y,z))$ 의 식을 계속 진행하여 전체 경로에 대한 최단 경로를 알아낸다.

//최단 경로 수도 코드
//입력 : 가중치 그래프 G
//출력 : distance 배열, distance[u]는 v에서 u까지의 최단 거리
shortest_path(G,v)
    S = v;
	for(G의 각 정점 w) do
        distance[w] = weight[v][w];
	while 모든 정점이 S에 없음
        u = 집합 S에 속하지 않는 정점 중 최소 distance 정점;
		S = S U u
            for(u에 인접하고 S에 있지 않는 각 정점 z) do
                if (distance[u] + weight[u][z] < distance[z])
                    then distance[z] = distance[u] + weight[u][z]

시간 복잡도를 살펴보면,n개의 정점이 있을때, n번씩 반복하며 경로를 2n번 분석하므로 O($n^2$)이다.

 

최단경로 (플로이드)

여기에 모든 정점 끼리의 최단 경로를 구하려면 이런 다익스트라의 알고리즘을 사용할 수 있다.
하지만 이를 더 간단하게 한 플로이드의 알고리즘도 있다.
단순하게 weight들이 담긴 2차원 배열을 3중 반복하는 루프로 구성되어 있다.
초기값은 각 weight이고, i==j면 0, 간선이 없으면 INF이다.

floyd(G)
	for k=0 to n-1
		for i=0 to n-1
			for j=0 to n-1
				A[I][J] = MIN (A[i][j],A[i][k]+A[k][j])

0~k까지만의 정점을 사용하여 i에서 j로 가는 최단경로는
$A^{k-1}[i][j] = min(A^{k-1}[i][j], A^{k-1}[i][k]+A^{k-1}[k][j])$ 이기 때문에 계속해서 재귀 호출하여 최소값을 갱신하는 방법이다.

다익스트라의 시간복잡도가 O($n^2$)일때, 모든 정점끼리를 하기 위해선 n번 반복해야 하므로 O($n^3$)이 소요된다. 플로이드 역시 삼중 for문으로 O($n^3$)의 시간복잡도이지만, 훨씬 간결하기 때문에 모든 정점간 최단 경로를 찾을 때는 더 효율적이다.

 

MST (프림)

Spanning Tree (신장 트리) 는 트리들 중에 모든 정점을 포함하는데, 트리이기 때문에 사이클이 존재하지 않는 그래프를 의미한다.
이러한 트리들 중에서 간선에 가중치(weight)를 부여했을때, 이 가중치들의 합이 최소인 신장 트리가 MST(Minimun Spanning Tree) 이다.
컴퓨터 알고리즘에서 최단 경로를 찾아내듯 가중치를 담은 그래프를 사용할 일은 많다.
이때 가중치들의 합이 최소가 되면서, 모든 정점을 연결하는 그래프를 찾아내는 것은 중요하다.

프림은 정점을 중심으로 알고리즘을 진행하는데, 그래프의 노드들을 세 가지로 분류해서 알고리즘을 진행시킨다.

Tree : 트리에 속해있는 노드

Fringe : 트리와 인접한 노드들

Unseen : 나머지 발견 안된 노드들

처음엔 시작 정점을 Tree에 넣고 시작한다.

1. Tree와 Fringe를 연결한 간선중 최소를 선택한 뒤 Fringe를 추가시킨다.
2. Unseen 노드들 중 인접한 노드를 Fringe에 추가시킨다. 이때 간선 중 최소 값도 저장해놓는다.

//MST를 구하는 프림 알고리즘 수도 코드, 출력은 정점 집합
//G =(V,E), n은 노드의개수, s 시작점
Prim(G,s)
	Vt = s; vcounter = 1;
	while (vcounter < n) do
   	 	(u,v)는 u가 Vt에 속하면서 v가 Vt에 속하지 않는 최저비용 간선;
		if((u,v) 존재)
        	then Vt = Vt U u; vcounter = vcounter+1;
		else 실패
	return Vt

A에서부터 시작해서 Fringe중 가장 작은 가중치의 B를 선택

Fringe를 계속 갱신해가며, 가장 작은 값을 가지는 정점을 계속 포함 

최종적으로 모든 노드가 트리에 선택되면 종료.

이때 Fringe에서의 최소값들을 추가시켰을 때 이 트리가 MST임을 증명해보자.

그래프 G(V,E,W)가 있고, MST의 일부분인 트리 T가 있다고 가정하자. 이때 이 트리의 x, y점을 연결하는 xy가 최소의 weight라 할때 이 간선을 포함시킨 트리 T' 역시 MST의 일부분이다.

증명으로 만약 xy가 이미 T에 속해있으면 바로 성립한다.
만약 T에 속해있지 않는다고 생각하자. x에서 y로 가는 다른 경로가 있어서 사이클을 형성해 추가하지 않은 것이다.
그 경로의 첫번째 간선을 vw라 하고, 이 간선을 따르는 트리를 T'이라 하자.
여기서 프림 알고리즘의 특성상 vw 역시 v가 T'에 속해있고, w가 T'에 속해있지 않다. 그렇다면 vw보다 xy의 가중치가 더 작으므로 xy를 선택한 트리가 더 MST에 근접하다. 따라서 T < T' 이므로 최소값인 간선 xy를 추가시킨 트리가 MST이다.

이러한 프림의 탐색 방법은 자료형에 따라 시간복잡도가 다르게 나온다.
정확히는 최소 Fringe를 찾아내게 하는 큐의 구현에 따라 다른데 먼저 위의 알고리즘을 시간복잡도는 다음과 같이 표현할 수 있다.
$O(V)T + O(E)T$
즉 (1번) 정점 개수 X Fringe 별 간선 중 최소 값을 찾는 시간 + (2번) 간선 개수 X Fringe의 간선을 최소 값으로 변경하는 시간이다.

여기서 Binary Heap을 사용한다면, 최소 값을 찾는데 O(lgV)번 걸리고, 변경하는데도 O(lgV)번 걸리므로 O(VlgV) + O(ElgV) = O(ElgV)번이 소요된다.

만약 배열을 사용한다면, 최소 값을 찾는데 일일히 비교하므로 O(V)번이지만, 각 Fringe별 간선의 최소값으로 변경하는데는 모든 정점을 탐색하지 않아도 되므로 O(1)이 소요된다. (이미 다 저장되어 있으므로) 따라서 O($V^2$) + O(E ) = O($V^2$) 이 소요된다.

 

MST (크루스칼)

프림이 정점 위주로 진행하였다면, 크루스칼은 간선 위주로 진행하는 방법이다.

탐욕 방법 (Greedy Method)를 사용해서 당장 최선의 선택이 최종적으로 최선이 될 수 있게, 시작 정점에서부터 단계적으로 확장해나간다.
모든 간선을 정렬한 후 최소의 간선들을 순서대로 선택하는데, 이 간선들 중 cycle을 형성하는 간선들은 제외하면서 선택한다. ('union-find' 알고리즘 사용)

//MST를 구하는 크루스칼 알고리즘 수도 코드, 출력은 간선 집합
//G =(V,E), n은 노드의개수
kruskal(G)
	E를 w(e1) <= ... <= w(ee)가 되도록 정렬
	Et = 시작점; encounter = 0; k=0;
	while(encounter < n-1) do
    	k = k+1
    	if(Et U ek가 사이클을 포함하지 않으면)
        	then Et = Et U ek; encounter = encounter+1;
	return Et

크루스칼 알고리즘의 시간복잡도를 좌우하는 것은 두가지이다.
간선들 중 최소값으로 정렬하는 복잡도 + 사이클 체크하는 복잡도.
여기서 union-find 알고리즘의 복잡도가 최적화 시 O(lgV)가 소요되므로, 결국 간선들을 정렬하는 최소의 시간복잡도인 O(ElgE)가 소요됨을 알 수 있다.

따라서 그래프의 간선이 많은 밀집 그래프(Dense Graph)라면 프림 알고리즘을, 정점 대비 간선이 별로 없는 희소그래프(Sparse Graph)라면 크루스칼 알고리즘을 사용하는 것이 효율적으로 MST를 찾을 수 있다.

또한, 같은 그래프라도 프림/크루스칼의 MST가 다를 수 있다.