[알고리즘] 그래프 알고리즘

1. 최소 신장 트리

1) 정의

신장트리란 가중 무방향 그래프에서 모든 정점을 포함하는 트리를 의미합니다. 

즉 정점이 n개라면 트리에는 n-1개의 간선이 존재합니다. 

 

이 중 최소(비용) 신장 트리는 아래와 같은 정의를 만족하는 트리입니다.

2) 최소 신장 트리를 구하는 알고리즘

모든 간선 중에서 정점을 모두 연결하면서 가중치의 합을 가장 작게 만드는 (n-1)개의 간선을 고르는 과정이라고 할 수 있습니다.

 

Greedy_MST ( G )
  {
  T ← Ø ; // 최소 신장 트리의 간선 집합
  while ( T가 신장 트리를 만들지 않았음 ) {
  최선의 간선 (u, v) 선택;
  T ← T ∪ { (u, v) }; 
  }
  return (T);
  }

위 코드에서 최선의 간선이라는 것은 사이클을 형성하지 않으며 최소의 가중치를 갖는 간선입니다.

 

이러한 최소 신장 트리를 구하는 알고리즘은 욕심쟁이 방법을 적용하며 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있습니다.

 

3) 크루스칼 알고리즘

간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 골라서 사이클을 형성하지 않으면 해당 간선을 추가하는 방식으로 알고리즘을 진행합니다.

 

이 때 간선 (u,v)의 두 정점 u,v가 서로 다른 연결 성분에 속하면 사이클을 형성하지 않는 것입니다.

 

|V| = n개의 정점이 각각의 서로 다른 연결성분으로 구성된 상태에서 시작해서 간선을 추가할 때마다 연결성분들이 하나씩 합쳐지고 최종적으로 하나의 연결성분을 형성합니다.

 

1]알고리즘

Kruskal ( G )
  { 
  T = Ø; //O(1)
  for ( G의 각 정점 v에 대해 ) // O(|V|)
   정점 v로 구성된 연결 성분 초기화;
   가중치가 증가하는 순으로 모든 간선을 정렬; //O(E|log|E|)
  for ( 가중치가 가장 작은 간선부터 모든 간선 (u, v) ∈ E에 대해서 ) //O(|E|)
    if ( u와 v가 서로 다른 연결 성분에 속하면 ) { //사이클을 형성하지 않으면// // 성능: O(|E|log|E|)
      T = T ∪ { (u, v) };
      u가 속한 연결 성분과 v가 속한 연결 성분을 합침;
    }
    else 간선 (u, v)를 버림;
  return (T);
  }

 

따라서 크루스칼 알고리즘의 성능은 O(|E|log|E|)가 됩니다.

 

2] 알고리즘 수행예제

예제1)

위와 같은 그래프가 주어졌을 때 최소 신장 트리인 크루스칼 알고리즘을 구해보겠습니다.

 

첫번째로 연결 성분을 초기화하고 두번째로 가중치가 낮은 것부터 높은 순으로 간선을 정렬합니다.

 

위 순서에서는 사이클이 형성되기 때문에 제외합니다.

위 순서에서는 사이클이 형성되기 때문에 제외합니다.

위 순서에서는 사이클이 형성되기 때문에 제외합니다.

위 순서에서는 사이클이 형성되기 때문에 제외합니다.

 

예제2)

4) 프림 알고리즘

임의의 한 정점에서 시작해서 연결된 정점을 하나씩 선택해 나가는 방법입니다.

이미 선택된 정점들에 부수된 가중치가 가장 작은 간선을 선택해서 추가합니다. 어떤 순간에 이미 선택된 정점의 집합 S와 선택되지 않은 정점의 집합 V-S를 잇는 간선 중에서 가중치가 가장 작은 간선을 선택해서 추가하는 방법이라고도 할 수 있습니다.

즉 임의의 정점 하나를 S로 지정한 후 시작해서 S=V가 될때까지 S를 점점 키워 나가는 방법입니다.

 

1] 알고리즘

 Prim ( G )
  { 
    T = Ø; 
    S = { 1 }; // 임의의 정점(예, 여기서는 1)으로 초기화
    while ( S != V ) {
      u ∈ S, v ∈ V-S인 것 중 가중치가 최소인 간선 (u, v) 선택;
      T = T ∪ { (u, v) };
      S = S ∪ { v };
    } 
    return (T);
  }

 

2] 알고리즘 수행예제

예제1)

1에서 선택되지 않은 정점 중 가중치가 가장 작은 것은 1-3이므로 정점 3이 선택됩니다.

정점 1,3의 간선 중 선택되지 않은 간선 중 가장 가중치가 낮은 것은 3-5 또는 3-6입니다. 순서는 둘 중 하나로 해도 상관없습니다. 여기서는 정점 5를 먼저 선택했습니다.

정점 1,3,5의 간선 중 선택되지 않는 간선에서 가중치가 가장 낮은 것은 3-6이므로 정점 6을 선택합니다.

정점 1,3,5,6의 간선 중 선택되지 않은 간선에서 가중치가 가장 낮은 것은 2-5, 3-4입니다. 따라서 둘 중 아무거나 선택해도 되지만 여기서는 정점 2를 선택했습니다.

정점 1,2,3,5,6의 간선 중 선택되지 않은 간선에서 가중치가 가장 낮은 것은 3-4입니다. 따라서 정점 4를 선택합니다.

모든 정점이 선택되었으므로 종료하고 가중치의 합을 계산합니다.

 

예제2)

프림 알고리즘은 어떤 자료구조를 사용하느냐에 따라 성능이 달라집니다.

 

인접행렬일 경우 O(|V|^2)이 되며 인접리스트와 힙을 사용한 경우 O((|V|+|E|)log|V|)가 됩니다.

2. 최단 경로

두 정점 u,v간의 최단 경로라는 것은 가중 그래프에서 두 정점 u에서 v를 연결하는 경로 중 간선의 가중치의 합이 가장 작은 경로입니다

 

최단 경로 문제의 유형에서는 단일 출발점 최단 경로 문제, 단일 도착점 최단 경로 문제, 단일 쌍 최단 경로 문제, 모든 쌍 최단 경로 문제 등이 있습니다.

 

이 중 단일 출발점 최단 경로 문제에는 데이크스트라 알고리즘과 벨만-포드 알고리즘이 있으며 모든 쌍 최단 경로 문제에는 플로이드 알고리즘이 있습니다.

 

1) 데이크스트라 알고리즘

데이크스트라 알고리즘은 하나의 출발 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.

이 알고리즘도 욕심쟁이 방법이 적용되어 있으며 음의 가중치를 갖는 간선이 없다는 가정을 하고 사용합니다. 따라서 간선 중 음의 가중치를 갖는 간선이 있다면 데이크스트라 알고리즘을 사용할 수 없습니다.

 

이 알고리즘에서는 거리 d[v]를 사용합니다. 거리는 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이를 의미합니다.

 

따라서 데이크스트라 알고리즘은 출발점에서 시작하여 거리 d[]가 최소인 정점을 차례대로 선택하여 최단 경로를 구하는 방법이라고 할 수 있습니다.

 

가장 먼저 초기화를 합니다. 초기화는 출발점 s의 거리 d[s] = 0, 나머지 모든정점 v의 거리 d[v] = ∞ 로 하며 선택된 정점의 집합 S={} 로 합니다.

 

S=V가 될때까지 반복하는데 미선택 집합 V-S에서 거리 d[]가 가장 작은 정점 u를 선택합니다. 이 때 u의 인접 정점에 대해서 u를 경유하는 거리와 기존거리를 비교해서 작은 값을 새로운 거리값으로 조정합니다.

 

1]알고리즘

Dijkstra (G, s) //G=(V,E),s : 시작 정점
  {
    S = { }; d[s] = 0; 
    for ( 모든 정점 v∈V ) { 
      d[v] = ∞; 
      prev[v] = NULL;
    }
    while (S != V) {
      d[u]가 최소인 정점 u ∈ V-S를 선택; 
      S = S ∪ { u };
      for ( u에 인접한 모든 정점 v ) 
        if ( d[v] > d[u] + W(u, v) ) {
        d[v] = d[u] + W(u, v);
        prev[v] = u;
      }
    } 
    return (d[ ], prev[ ]); 
    //d[] : s로부터 다른 모든 정점으로의 최단 경로의 길이\
    //prev[] : 최단 경로를 만드는 선행 정점
  }

 

2] 알고리즘 수행예제

예제1)

출발정점의 거리를 0으로 만들고 나머지 정점을 무한대로 만듭니다. 그리고 선택된 집합S를 공집합으로 만듭니다.

 

출발점 1에서 이동가능한 정점의 거리가 간선의 값으로 변경됩니다.

 

 

거리 가장 가까운 2가 두번째로 선택되며 2의 인접한 정점은 3,4가 있습니다. 이 때 1에서 바로 3으로 가는 것보다 1에서 2를 거쳐서 3으로 가게되면 1+5가 되어 d[3] = 6이 됩니다. 그리고 1에서 2를 거쳐 4로 가게되면 1+2 = 3이 되므로 d[4] = 3으로 바뀌게 됩니다.

2에서 거리값이 가장 가까운 것은 4가 되며 4에서 인접한 정점 중 3,5가 있습니다.

이 때 1-3 = 7이지만 1-2-4-3 = 1+2+2 = 5가 되므로 작은 거리로 선택되어 d[3] = 5가 되고 

마찬가지로 1-5 = 6이지만 1-2-4-5 = 1+2+2 = 5가 되어 d[5] = 5가 됩니다.

 

4에서 거리값이 가장 가까운 정점은 5가 되며 5에서 인접한 정점은 3,6이 있습니다. 

d[6]=1-2-4-5-6 = 1+2+2+3 = 8이 되고 d[3] = 1+2+2+2 = 7이 되는데 기존 거리인 d[3] = 5이므로 거리가 변하지 않습니다.

같은 방식으로 거리를 줄여나갑니다.

 

예제2)

예제1은 방향 그래프라서 방향이 정해져있지만 예제2는 무방향 그래프이기 때문에 양방향으로 이동할 수 있습니다.

데이크스트라 알고리즘의 성능은 인접행렬일 경우 O(|V|^2)가 되며 인접리스트와 힙을 사용할 경우 O((|V|+|E|)log|V|)가 됩니다.

 

이 때 데이크스트라 알고리즘은 음의 가중치를 간선이 없어야하는데 어떤 문제가 발생하는지 아래 예제를 통해 확인해보겠습니다.

이 때 마지막 그림을 살펴보면 결과로는 d[3] = 3이 나옵니다. 그런데 만약 d[3] = 1이고 3-4는 1이므로 d[4] = 2가 되어야합니다. 이렇게 결과가 왜곡되는 문제가 발생할 수 있습니다.

 

2)벨만-포드 알고리즘

벨만-포드 알고리즘은 데이크스트라 알고리즘과 달리 음의 가중치를 갖는 간선이 존재하는 경우에도 처리 가능합니다. 그러나 음의 사이클은 존재하면 안됩니다.

 

1] 알고리즘 수행방식

G = (V,E)에서 |V| = n일 때 단계적으로 최단경로를 구해나갑니다.

 

처음 초기화는 출발점 s의 거리 d[s] = 0, 나머지 정점 v의 거리 d[v] = ∞로 합니다.

 

두번째로 아래 그림처럼 수행합니다.

 

2] 알고리즘

Bellman_Ford (G, s) {
  for ( 모든 정점 v ∈ V ) {  //O(|V|)
    d[v] = ∞; 
    prev[v] = NULL;
  }
  d[s] = 0;
  for (i=1; i<n; i++) { //O(|V|)
    for ( 모든 간선 (u, v) ∈ E ) // O(|E|)
      if ( d[v] > d[u] + W(u, v) ) {
        d[v] = d[u] + W(u, v);
        prev[v] = u;
      }
    } 
    return (d[ ], prev[ ]);
  }

따라서 성능은 O(|V||E|)가 됩니다.

 

따라서 음의 가중치가 있는 경우 벨만-포드 알고리즘이 더 효율적이며, 음의 가중치가 없는 경우 데이크스트라 알고리즘이 더 효율적입니다.

 

3] 알고리즘 수행예제

예제1)

간선 1개를 사용한 최단경로는 1-2와 1-3이므로 두 정점 까지의 거리를 구합니다. → d[2] = 4, d[3] = 2

간선 2개를 사용한 최단경로는 1-2-3 과 1-3-4이므로 각각의 거리를 구합니다. → d[3] = 4-3=1, d[4] = 2+1=3

간선 3개를 사용한 최단경로는 1-2-3-4의 거리를 구합니다. → d[4] = 4-3+1 = 2

 

예제2)

 

3) 플로이드 알고리즘

이 알고리즘은 경로의 길이가 음인 사이클은 존재하지않는다고 가정하고 있고 동적프로그래밍 방법을 적용합니다.

 

수행방식은 경유할 수 잇는 정점의 범위가 1인 경로부터 시작해서 |V|인 경로까지 하나씩 정점의 범위를 늘려가면서 모든 정점 간의 최단 경로를 한꺼번에 구합니다.

 

플로이드 알고리즘은 인접행렬 표현을 활용합니다.

1] 알고리즘

Floyd (G) 
  {
    for (i=1; i<=n; i++) 
      for (j=1; j<=n; j++) 
        D[i][j] = A[i][j]; 
    for (k=1; k<=n; k++) // D(k): 경유하는 정점 k
      for (i=1; i<=n; i++) 
        for (j=1; j<=n; j++) 
          if (D[i][j] > D[i][k] + D[k][j] ) // 경유하는 경우
            D[i][j] = D[i][k] + D[k][j];
    return (D[ ][ ]); 
  }

최대 중첩은 3중 반복문이므로 성능은 O(n^3)이 됩니다. 이때 n = |V|라고도 하므로 O(|V|^3)으로 표현할 수도 있습니다.

 

2] 알고리즘 수행예제

예제1)

예제2)

3] 특징

3. 네트워크 플로 문제

네트워크 플로 문제란 주어진 네트워크에 대해서 플로를 최대로 하는 값을 찾는 문제입니다.

즉, 소스에서 싱크로 보낼 수 있는 플로값을 최대로 하는 문제라고 할 수 있습니다.

 

이 때 네트워크 N = (V,E,s,t,c)

방향 그래프 G = (V,E)이며

s는 소스입니다. 소스란 시작점이며, 진입차수가 0인 정점입니다.

t는 싱크입니다. 싱크란 도착점을 의미하며 진출차수가 0인 정점입니다.

c는 간선의 가중치입니다. 네트워크 플로 문제에서는 가중치를 간선의 용량이라고 합니다.

 

이를 조합해서 c(u,v)라고 표현하는데 이는 간선 u,v를 통해 보낼 수 잇는 최대의 양 또는 값입니다.

 

 

1) 포드-풀커슨 알고리즘

최초로 제시된 가장 기초적인 해결방법입니다.

단순히 플로 값을 증가시킬 수 있는 모든 경우의 수를 탐색해서 적용합니다. 단점으로는 종료가 보장되지 않아서 추후에 에드몬즈-카프 알고리즘으로 발전합니다.

 

1] 수행방법

모든 간선의 플로를 0으로 둔 상태에서 시작해서 증가경로가 더 이상 존재하지 않을 때까지 반복적으로 경로를 찾아서 최대 플로값을 구합니다.

 

이 때 증가경로란 소스에서 싱크까지 더 많은 플로를 보낼 수 있는 경로를 의미합니다. 그런데 이 증가경로상의 간선이 네트워크 N의 간선방향과 일치하지 않을 수 있습니다.

 

 

2] 알고리즘

 

3] 알고리즘 수행 예제

예제1)

 

1-4는 3까지 사용할 수 있는데 현재 사용량이 0이므로 잔여용량은 3입니다.

s-3는 6까지 사용할수있는데 4만큼 사용했으므로 잔여용량이 2가 됩니다.

2-t는 5까지 사용할 수 있는데 현재 사용량이 4이므로 잔여용량은 1입니다.

4-t는 7까지 사용할 수 있는데 현재 사용량이 5이므로 잔여용량은 2가 됩니다.

이때 2-3은 역방향 간선이므로 3-2를 2만큼 차감하고 2-3은 -2 / 0이 됩니다.

 

따라서 소스에서 나가는 값인 s-1,s-3의 합인 6+6 = 12 그리고 싱크로 들어오는 값인 2-t, 4-t의 합인 5+7=12가 됩니다.

 

예제2)

4] 성능과 특징

 

포드-풀커슨 알고리즘에는 문제점이 있습니다. 

 

첫번째로 용량으로 무리수를 사용하므로 알고리즘의 종료를 보장할 수 없습니다.

 

두번째로는 용량M이 매우 크다면 비효율적입니다.

증가경로의 선택은 DFS 또는 BFS를 적용하는데 포드-풀커슨 알고리즘에서는 기본적으로 DFS를 적용하여 증가경로를 선택합니다. 

 

포드-풀커슨 알고리즘에서는 커트라는 개념이 있습니다. 

결론적으로 말하면 어떤 커트든 커트의 용량은 최대플로값과 같습니다.

이 커트는 포드-풀커슨 알고리즘에서 정확성을 검증하는데 많이 사용합니다.