[SW Expert Academy] Advanced-6 그래프의 최소 비용 문제
그래프의 비용 문제는 확실히 다잡아야 한다. 크게 최소 신장 트리 문제, 최단 경로 문제가 있다.
최소 신장 트리란 가중치 그래프에서 모든 정점들을 연결하는 간선들의 가중치의 합이 최소가 되는 트리를 찾는 문제이다.
반면, 최단 경로 문제란 시작 정점서 목표 정점까지 가는 가중치의 합이 최소가 되는 경로를 찾는 문제이다.
최소 신장 트리란 가중치 그래프에서 모든 정점들을 연결하는 간선들의 가중치의 합이 최소가 되는 트리를 찾는 문제이다.
반면, 최단 경로 문제란 시작 정점서 목표 정점까지 가는 가중치의 합이 최소가 되는 경로를 찾는 문제이다.
플로우 1. 최소 신장 트리 (프림 알고리즘, 크루스칼 알고리즘) 2. 최단 경로 (다익스트라 알고리즘)
1. 최소 신장 트리
신장 트리: V개의 정점을 포함하는 무향 그래프에서 V개의 정점과 V-1개의 간선으로 구성된 트리
1-1. 프림(Prim) 알고리즘
-한 정점에 연결된 간선들 중, 최소 가중치를 가지는 간선을 선택하면서 최소 신장 트리를 만들어나가는 방식
1) 임의의 정점을 하나 선택
2) 선택한 정점들과 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점을 선택
3) 모든 정점이 선택될 때까지 앞의 과정을 반복
-수도 코드 (사이트 코드를 이해할 수 없어서 구현한 코드로 대체 - 1251문제 답)
//parent[MAX_V]: 최소 신장 트리
//weight[MAX_V]: 선택된 정점 집합으로부터의 현재까지의 최소 가중치
//vector<G_NODE> adj[MAX_V]: 그래프 (G_NODE={weight, target vertex})
//vector<PQ_NODE> pq: 우선 순위 큐 (PQ_NODE = {weight, parent})
//visited[MAX_V]: 탐색한 정점들의 집합을 나타냄
MST_PRIM(G,r): // G:그래프, r:시작정점
cost = 0
for all u in G.V: //우선순위 큐에 들어갈 pq_node = {weight, parent}
parent[u] = u
weight[u] = INF
visited[u] = 0
pq_cur.v = r //시작 정점
pq_cur.w = 0
pq.push(pq_cur) //
while pq is not empty: //더 빠르게 하려면 V-1번만 반복하게 하면 됨
pq_cur <- pq.top()
v_cur <- pq_cur.v
w_cur <- pq_cur.w
pq.pop()
if visited[v_cur]: //벌써 탐색한 노드라면 탐색하지 않는다.
continue
visited[v_cur] = 1
for all v_next in ADJ(G,v_cur): //Graph에 들어갈 g_node = {weight, target vertex}
w_next <- weight of edge(v_cur, v_next)
if weight[v_next] > w_next:
weight[v_next] <- w_next //업데이트
parent[v_next] <- v_cur
pq.push({v_next, w_next})
-복잡도
|E|*log(|V|)
모든 정점은 정확히 한번 방문되고, 각 정점에 방문할 때마다 모든 인접 정점을 검사한다. 즉 모든 간선을 검사한다.
따라서 검사 복잡도가 O(|E|)이다.
두번째로, 우선순위 큐의 최대 크기를 봐야 한다. 최악의 경우, 인접 정점을 검사할 때마다 큐에 삽입해야 한다.
따라서 최대 크기는 |E|이고 삽입 복잡도는 O(log(|E|)이다.
그런데 여기서, 아무리 간선이 많아도 복잡도는 E < V^2이므로 O(log(|E|)) = O(log(|V|))라고 표현할 수 있다.
결과적으로 복잡도는 |E|*log(|V|)가 된다.
다익스트라알고리즘도 같은 논리로 전개된다. (사실상 코드가 거의 유사하다.)
1-2. 크루스칼(Kruskal) 알고리즘
-최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘
-cycle이 생기지 않아야 함
-V개의 정점을 포함하는 그래프에서 V-1개의 간선을 선택하는 방식
-간선을 선택하는 과정에서 여러 개의 트리 존재
사이클 확인 방법 (disjoint set을 이용)
-각 정점을 원소로 가지는 V개의 disjoint set이 존재
-간선을 선택하면 간선의 두 정점이 속한 트리가 연결되어 하나의 집합이 됨
-선택한 간선의 두 정점이 이미 연결된 트리에 속하는 정점이면 사이클이 생김
동작 과정
1)모든 간선을 가중치에 따라 오름차순으로 정렬한다.
2)가중치가 낮은 간선부터 선택하며 트리를 증가시킨다.
-사이클이 존재하면 다음 간선을 선택
3)n-1개의 간선이 선택될 때까지 앞의 과정을 반복
수도 코드
MST_KRUSCAL(G):
T <- NULL
for all v in G.v:
make_set(v)
간선들(G.E)를 가중치 순으로 오름차순 정렬
while T의 크기 < |V| -1:
가중치가 가장 낮은 (u, v)를 선택
if find_set(u) != find_set(v): //사이클이 없다면
T에 {(u,v)}간선을 포함
union(u, v)
return T
복잡도
O(|E|log(|V|))
간선들을 정렬하는 과정에서 O(|E|log(|E|)) = O(|E|log(|V|))가 걸림
2. 최단 경로
-간선의 가중치가 있는 유향 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로
-단일 시작점 최단 경로 문제 (단일 시작점으로부터 모든 정점까지의 최단 경로)
1) 다익스트라(Dijkstra) 알고리즘: 음의 가중치를 허용하지 않음
2) 벨만포드(Bellman-Ford) 알고리즘: 음의 가중치를 허용하지만, 가중치의 합이 음인 사이클은 허용하지 않음
-모든 쌍 최단 경로 문제
1) 플로이드-와샬(Floyd-Warshall) 알고리즘
2-1. 다익스트라 알고리즘
단일 시작점에서 거리가 최소인 정점부터 선택해나가면서 최단 경로를 구하는 방식
-수도 코드
//G: 그래프, r: 시작 정점, s: 선택된 정점 집합
//D: 출발점부터 각 정점까지의 최단 경로 가중치 합
//P: 최단 경로 트리 저장, ADJ(u): 정점 u의 인접 정점 집합
Dijkstra(G, r):
S <- NULL
for all v in V:
D[v] <- INF
P[v] <- NULL
D[r] <- 0
while S!=V:
D[u]가 최소인 정점 u를 V-S로부터 선택함 (우선순위 큐 이용하자)
S에 원소 {u} 포함
for all v in ADJ(u):
if v in V-S and D[v] > D[u]+weight(u,v):
D[v] <- D[u]+weight(u,v)
P[v] <- u
-복잡도
O(|E|log|V|)
위의 프림알고리즘과 같은 방식으로 복잡도 계산
2-2. 벨만-포드 알고리즘
음의 가중치를 포함하는 그래프에서 최단 경로를 구한다. (음의 사이클은 허용 불가)
1) 출발점에서 각 정점까지 간선 하나로 구성된 경로를 고려하여 최단 경로를 구한다.
2) 최대 간선 2개까지 고려하여 최단 경로를 구한다.
3) 최대 간선 n-1개까지 고려하여 최단 경로를 구함
->시간 소요가 많다.
Reference
댓글
댓글 쓰기