C++로 쉽게 풀어쓴 자료구조/ 가중치 그래프

가중치 그래프란?

간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프(weighted graph)라고 한다.

가중치 그래프는 수학적으로는 G = (V, E, w)와 같이 표현된다. V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미하고, w(e)는 간선 e의 강도(weight), 비용(cost), 또는 길이(length)라고 부른다. 어떤 가중치 그래프의 경로를 p = (v0, v1, v2, … vk)라고 한다면 경로의 강도 w(p)는 다음과 같이 경로 상의 모든 간선의 강도 합으로 표현된다.

가중치 그래프의 표현

가중치의 표현

가중치 그래프의 클래스에서는 인접 행렬을 약간 다른 용도로 사용해야 한다. 인접 행렬의 값을 간선의 유무가 아니라 간선의 가중치를 직접 나타내게 하면 가중치 그래프를 나타낼 수 있다.

그러나 이 경우 간선의 유무를 판단하기 어려워지는데, 이런 경우에는 간선의 유효 범위를 넘어서는 값을 지정하여 –예컨대 999999– 그 값 이상이 되면 간선이 없는 경우로 판단하여 처리하는 방법이 있다.

최소 비용 신장 트리

최소 비용 신장 트리란?

통신망, 도로망, 유통망 등은 대개 길이, 구축비용, 전송 시간 등의 가중치를 간선에 할당한 가중치 그래프로 표현할 수 있다. 이러한 망을 가장 적은 비용으로 구축하고자 한다면 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이 좋다. 이때 최소 비용 신장 트리(MST: minimum spanning tree)가 필요하다. 최소 비용 신장 트리는 어떤 그래프의 신장 트리들 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다. 최소 비용 신장 트리의 응용 예는 다음과 같다.

  • 도로 건설: 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
  • 전기 회로: 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제
  • 통신: 전화선의 길이가 최소가 되도록 전화망을 구성하는 문제
  • 배관: 원하는 모든 장소를 연결하면서 사용된 전체 파이프의 길이를 최소화하도록 연결하는 문제

최소 비용 신장 트리의 조건은 다음과 같다.

  1. 간선의 가중치의 합이 최소여야 한다.
  2. 반드시 (n-1)개의 간선만 사용해야 한다.
  3. 사이클이 포함되어서는 안 된다.

최소 비용 신장 트리를 구하는 방법에는 Kruskal과 Prim이 제안한 알고리즘이 대표적으로 사용된다.

Kruskal의 MST 알고리즘

Kruskal의 알고리즘은 탐욕적인 방법(greedy method)이라는 알고리즘 설계에서 중요한 기법 중의 하나를 사용한다. 이것은 어떤 결정을 해야 할 때마다 ‘그 순간에 최적’이라고 생각되는 것을 선택하는 방법이다. 물론 순간에 최적이라고 최종적으로 최적이라는 보장은 없다. 따라서 탐욕적인 방법은 항상 최적의 해답을 주는지를 반드시 검증해야 한다. 다행히 Kruskal의 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다.

kruskal()
1. 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
2. 가장 가중치가 작은 간선 e를 뽑는다.
3. e를 신장 트리에 넣을 경우 사이클이 생기면 삽입하지 않고 2번으로 이동한다.
4. 사이클이 생기지 않으면 최소 신장 트리에 삽입한다.
5. n-1개의 간섭이 삽입될 때까지 2번으로 이동한다.

그림 12.4의 동작 순서는 다음과 같다.

  1. 먼저 간선들을 가중치의 오름차순으로 정렬
  2. 간선 (a, f) 선택. 사이클이 없으므로 삽입. MST 전체 간선 1개.
  3. 간선 (c, d) 선택. 사이클이 없으므로 삽입. 전체 간선 2개.
  4. 간선 (b, g)를 선택. 사이클이 없으므로 삽입. 전체 간선 3개.
  5. 간선 (b, c)를 선택. 사이클이 없으므로 삽입. 전체 간선 4개.
  6. 간선 (d, g) 선택. 사이클 b, c, d, g, b가 형성되므로 무시.
  7. 간선 (d, e) 선택. 사이클이 없으므로 삽입. 전체 간선 5개.
  8. 간선 (e, g) 선택. 사이클 e, g, b, c, d, e가 형성되므로 무시.
  9. 간선 (e, f) 선택. 사이클이 없으므로 삽입. 전체 간선 6개이므로 종료.

사이클 검사는 아래 내용 참조

union-find 연산

사이클의 검사를 위해 먼저 union-find 연산의 개념을 알아보자. union(x, y)은 원소 x와 y가 속해있는 집합을 입력으로 받아 이들의 합집합을 만드는 연산이다. find(x) 연산은 여러 집합들 중에서 원소 x가 속해있는 집합을 반환하는 연산이다. 다음과 같이 6개의 정점 집합을 예로 들어 보자.

{1}, {2}, {3}, {4}, {5}, {6}

여기에 union(1, 4)와 union(5, 2)를 하면 집합은 다음과 같이 변경된다.

{1, 4}, {5, 2}, {3}, {6}

여기에 find(2)를 하면 {5, 2}가 반환된다. 이들 4개의 집합이 있을 떄 union(4, 5)와 union(3, 6)을 수행하면 전체 집합은 다음과 같아진다.

{1, 4, 5, 2}, {3, 6}

정점 집합은 어떻게 구현할 수 있을까? 집합을 구현하는데는 여러 방법 –비트 벡터, 배열, 연결 리스트 등– 을 사용할 수 있는데 가장 효율적인 방법은 트리이다. 이 경우 하나의 트리가 하나의 집합을 나타내고 트리의 노드들이 집합의 원소가 된다. 집합은 트리의 루트에 의하여 대표된다.

예컨대 {1, 4}, {5, 2}, {3}, {6}은 그림 12.6과 같이 표현되고 이어서 union(4, 5)와 union(3, 6)을 한다면 다음과 같이 트리가 변화하게 된다. find(4)를 한다면 루트인 정점 2가 집합의 대표로 반환되게 된다.

사이클이 존재하는지를 검사하기 위해 union과 find 연산을 사용한다. 간선 (u, v)는 정점 u와 v를 연결한다. (u, v)가 사이클을 만드는지를 검사하기 위해서는 u와 v가 같은 집합에 있는지를 확인해야 한다. 예컨대 그림 12.6의 오른쪽 그래프가 현재까지 만들어진 신장 트리라고 하자. 이때 간선 (3, 5)를 삽입하면 사이클이 생기지 않는다. 그러나 만약 간선 (4, 5)를 삽입하면 사이클이 생기는데 이유는 3과 5는 서로 다른 집합에 있고, 4와 5는 같은 집합에 있기 때문이다.

사이클을 검사하는 과정을 포함하여 Kruskal의 알고리즘을 다시 기술하면 다음과 같다.

  • 초기에는 모든 정점이 각각 고유한 집합이다.
  • 최소 가중치 간선 (u, v)가 선택되면 u와 v가 각각 속한 집합을 찾는다. 이때 find(u)와 find(v) 연산을 수행한다.
  • 두 집합이 같으면 사이클이 발생하는 상황이므로 이 간선을 버린다.
  • 두 집합이 다르면 간선을 삽입하고 집합을 하나로 합친다. 이때 union(u, v) 연산을 사용한다.

Kruskal의 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우된다. 따라서 퀵 정렬이나 최소 힙과 같은 효율적인 정렬 알고리즘을 사용한다면 Kruskal의 알고리즘의 시간 복잡도는 (|E|log2|E|)이다.

Prim의 MST 알고리즘

Prim의 알고리즘은 하나의 정점에서부터 시작하여 트리를 단계적으로 확장해나가는 방법이다. 처음에는 시작 정점만이 트리에 포함된다. 다음으로 지금까지 만들어진 트리에 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점을 선택하여 트리를 확장한다. 이 과정은 트리가 n-1개의 간선을 가질 때까지 계속된다.

Prim()
1. 그래프에서 시작 정점을 선택하여 초기 트리를 만든다.
2. 현재 트리의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점 v를 선택한다.
3. 이 정점 v와 이때의 간선을 트리에 추가한다.
4. 모든 정점이 삽입될 때까지 2번으로 이동한다.

Kruskal의 알고리즘이 간선을 기반으로 하는 알고리즘인데 비해 Prim의 방법은 정점을 기반으로 한다.

알고리즘의 순서는 다음과 같다.

  1. 시작 정점 a를 선택하고 트리에 넣는다. 전체 정점 1개
  2. 트리(회색 영역)와 이웃한 정점 f와 b 중에서 간선의 가중치가 작은 f를 선택하고 f와 간선 (a, f)를 트리에 넣는다. 전체 정점 2개.
  3. 트리와 이웃한 정점 b와 e 중에서 간선의 가중치가 작은 e를 선택하고 e와 간선 (f, e)를 트리에 넣는다. 전체 정점 3개.
  4. 트리와 이웃한 정점 b, d, g 중에서 간선의 가중치가 작은 d를 선택하고 d와 간선 (e, d)를 트리에 넣는다. 전체 정점 4개.
  5. 단계 5~7 같은 방법으로 정점 c, b, g를 순서대로 트리에 넣는다. 모든 노드가 삽입 되었으므로 종료.

Prim의 알고리즘은 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로 O(n2)의 시간 복잡도를 가진다. Kruskal의 알고리즘 복잡도가 O(elog2e)이므로 정점의 개수에 비해 간선의 개수가 매우 적은 희박한 그래프(sparse graph)를 대상으로 할 경우에는 Kruskal의 알고리즘이 적합하고, 반대로 간선이 매우 많은 그래프의 경우에는 Prim의 알고리즘이 유리하다고 할 수 있다.

최단 경로

최단 경로 문제란?

최단 경로(shortest) 문제는 가중치 그래프에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다.

가중치 그래프에서 정점들 사이의 최단 경로를 구할 수 있는 알고리즘으로는 Dijkstra와 Floyd의 2가지 알고리즘이 있다. Dijkstra 알고리즘은 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구하고 Floyd 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구할 수 있는 방법이다.

Dijkstra의 최단 경로 알고리즘

Dijkstra의 최단 경로 알고리즘은 하나의 시작 정점 v에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. 먼저 집합 S를 시작 정점 v로부터의 최단 경로가 이미 발견된 정점들의 집합이라고 하자. 이 알고리즘에서는 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단 거리를 기록하는 배열을 사용한다. 이 배열을 dist라고 하자. 당연히 시작 정점 v에서의 dist[v] = 0 이며, 다른 정점에 대한 dist 값은 시작 정점과 해당 정점 간의 간선의 가중치 값이 된다. 가중치는 인접 행렬에 저장되므로 인접 행렬을 weight이라 하면 최초에는 모든 정점 w에 대해 dist[w] = weight[v][w]가 된다. 정점 v에서 정점 w로의 직접 간선이 없을 경우에는 무한대의 값을 저장한다.

시작 단계에서는 아직 최단 경로가 발견된 정점이 없으므로 S = {v}일 것이다. 즉, 처음에는 시작 정점 v를 제외하고는 최단 거리가 알려진 정점이 없다. 알고리즘이 진행되면서 최단 거리가 발견되는 정점들이 하나씩 S에 추가된다.

알고리즘의 매 단계에서 S 안에 있지 않은 정점들 중에서 가장 dist 값이 작은 정점을 그림 12.10과 같이 S에 추가한다.

새로운 정점 u가 S에 추가되면, S에 있지 않은 다른 정점들의 dist 값을 수정해야 한다. 새로 추가된 정점 u를 거쳐서 정점까지 가는 거리와 기존 거리를 비교하여 더 작은 거리로 dist를 수정한다. 즉, 다음과 같은 수식을 이용한다.

dist[w] = min(dist[w], dist[u]+weight[u][w])

최단 거리 알고리즘을 정리하면 다음과 같다.

shortestPath(v)
    S <- {v}
    for 각 정점 w ∈ G do
        dist[w] <- weight[v][w];
    while 모든 정점이 S에 포함되지 않으면 do
        u <- 집합 S에 속하지 않은 정점 중에서 최소 distance 정점;
        S <- S ∪ {u}
        for u에 인접하고 S에 있지 않은 각 정점 z do
            if dist[u] + weight[u][z] < dist[z]
                then dist[z] <- dist[u] + weight[u][z];

Step 1: 초기 상태에는 S에 A만 들어 있다. dist는 모두 A에서 그 정점으로 가는 거리 w(A, v)가 된다.

Step 2: dist 배열에서 가장 작은 정점 E를 S에 추가한다. 이제 E까지의 거리는 확정된다. S에 포함되지 않은 나머지 정점에 대해서는 현재까지의 dist(v)와 새로 추가된 E에 의해 바뀔 수 있는 거리 dist(E)+w(E,v)를 비교하여 작은 값으로 dist(v)를 갱신한다.

Step 3: 같은 방법으로 dist 값이 가장 작은 B가 S에 추가된다. 나머지 정점의 dist 값을 갱신한다.

Step 4: 같은 방법으로 G가 S에 추가된다.

Step 5: 같은 방법으로 C가 S에 추가된다. 이제 거리가 확정되지 않은 정점은 D와 F만 남았다.

Step 6: 같은 방법으로 F가 S에 추가된다.

Step 7: 마지막으로 D가 S에 추가되고 남은 정점은 없다. A에서 모든 정점들까지의 거리가 확정되었다.

Dijkstra 알고리즘은 실행 결과로서 시작 정점으로부터 다른 정점까지의 최단 경로의 거리 정보만을 제공한다. 위의 프로그램의 효율성을 높이기 위해서는 최솟값을 선택하는 chooseVertex() 함수를 우선순위 큐로 대치하면 더 빠르게 수행시킬 수 있다. 그래프에 n개의 정점이 있다면, 최단 경로 알고리즘은 주 반복문을 n번 반복하고 내부 반복문을 2n번 반복하므로 O(n2)의 시간 복잡도를 가진다.

Floyd의 최단 경로 알고리즘

Floyd 알고리즘은 그래프의 모든 정점 사이의 최단 경로를 한꺼번에 찾아준다. Floyd의 최단 경로 알고리즘은 2차원 배열 A를 이용하여 3중 반복을 하는 루프로 구성되어 있다. 알고리즘 자체는 아주 간단하다. 먼저 인접 행렬 weight는 다음과 같이 만들어진다. u == v이면 weight[u][v] = 0 으로 하고 만약 두 정점 u, v 사이에 간선이 존재하지 않으면 weight[u][v] = ∞ 라고 하자. 정점 u와 v 사이에 간선이 존재하면 물론 weight[u][v]는 간선 (u, v)의 가중치가 된다. Floyd 알고리즘은 다음과 같이 간단한 3중 반복문으로 표현된다. A의 초기 값은 인접 행렬인 weight가 된다.

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])

위의 알고리즘을 설명하기 위해 Ak[i][j]를 0부터 k까지의 정점만을 이용한 정점 i에서 j까지의 최단 경로라고 하자. 우리가 원하는 답은 An-1[i][j]가 된다. 왜냐하면 An-1[i][j]은 0부터 n-1까지의 모든 정점을 이용한 최단 경로이기 때문이다. Floyd 알고리즘의 핵심적인 내용은 A-1 -> A0 -> A1 -> A2 -> … -> An-1 순으로 최단 거리를 구하는 것이다. A-1는 weight 배열의 값과 같다.

수학적인 귀납법과 비슷한 방법을 사용하여 생각해 보자. 먼저 Ak-1까지는 완벽한 최단 거리가 구해져 있다고 가정하자. 일반적으로 그림 12.13과 같이 k번째 정점이 추가로 고려되는 상황을 생각하여 보자. 0부터 k까지의 정점만을 사용하여 정점 i에서 정점 j로 가는 최단 경로는 다음의 2가지의 경우로 나눠서 생각할 수 있다.

  • 정점 k를 거치지 않는 경우: Ak[i][j] <- Ak-1[i][j]
  • 정점 k를 통과하는 경우: Ak[i][j] <- Ak-1[i][k] + Ak-1[j][k]

따라서 최종적인 최단 거리는 위 2개의 값 중 더 적은 값이 될 것이다.

Ak[i][j] <- min(Ak-1[i][j], Ak-1[i][k] + Ak-1[j][k])

이것은 정점 k를 경유하는 것이 보다 좋은 경로이면 Ak-1[i][j]의 값이 변경되고, 그렇지 않으면 이전 값을 유지한다는 의미이다.

그림 12.14는 예제 그래프에 대하여 A 배열이 변경되는 모습이다.

하나의 정점에서 출발하여 모든 정점까지의 최단 경로를 찾는 Dijkstra의 알고리즘은 시간 복잡도가 O(n2)이다. 따라서 모든 정점에서 출발한다면 Dijkstra의 알고리즘을 n번 반복해야 하므로 전체 복잡도가 O(n3)이 된다. 한 번에 모든 정점 간의 최단 경로를 구하는 Floyd의 알고리즘은 3중 반복문이 실행되므로 시간 복잡도가 O(n3)으로 표현되므로 Dijkstra 알고리즘과 차이는 없다. 그러나 Floyd 알고리즘은 매우 간결한 반복 구문을 사용한다는 특징이 있다.

It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기