최소 신장 트리(Minimum Spanning Tree)

최소 신장 트리(Minimum Spanning Tree)

• 가중치 그래프에서, 사이클 없이 모든 점을 연결시킨 트리들 중에 가중치 합이 최소인 트리를 의미한다.

• 그래프의 점의 수가 n이면, 신장트리에는 (n - 1)개의 선분이 존재한다.

  • n개 이상의 선분이 존재할 경우 사이클이 생기고, 이는 트리라고 할 수 없다.

• 대표적인 그리디 알고리즘으로 크러스컬(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 존재한다.

  • 입력으로 받는 그래프 G에는 점의 집합 V와 선분 집합 E에 대한 정보가 포함되어 있다.

  • 점의 개수를 n, 선분의 개수를 m이라고 가정한다.

---

크러스컬(Kruskal) 알고리즘

• 최소 가중치를 가진 선분을 하나씩 뽑아서, 트리에 사이클을 형성하지 않는지 검사하고 추가하는 방식이다.

  Pseudo Code

  KruskalMST(Graph g)
  {
    가중치의 오름차순으로 선분들을 정렬하여 L에 저장한다.
    Tree t;
    while (t의 선분 수 < (점의 개수 n) - 1)
    {
      선분 e = 가장 작은 가중치를 가진 선분을 가져오고 L에서 제거한다.
      if (선분 e가 사이클을 형성하지 않으면)
        선분 e와 그를 구성하는 점들을 T에 추가시킨다.
    }
    return t;
  }

시간복잡도

• 선분들을 정렬하는 데에 걸리는 시간은 O(mlogm)이다.

• 반복문은 최대 m번 수행되고, 각각의 루프 내에서 선분이 사이클을 형성하는지 검사하는데 O(log*m) 시간이 걸리므로 반복문에서는 총 O(mlog*m)의 시간이 걸린다.

  • log*m은 반복 로그를 의미하는데, 굉장히 느리게 증가하는 함수이다.

  • 참고 : https://ko.wikipedia.org/wiki/%EB%B0%98%EB%B3%B5_%EB%A1%9C%EA%B7%B8

• 따라서 크러스컬 알고리즘의 시간 복잡도는 O(mlogm)이다.

---

프림(Prim) 알고리즘

• 최소 가중치의 점을 트리에 포함시키며 계속해서 점과 점 사이의 가중치를 업데이트하는 방식이다.

  Pseudo Code

  PrimMST(Graph g)
  {
    최소 가중치를 저장해둘 배열을 D로 설정하고, 임의의 점 p를 골라서 D[p] = 0로 놓는다.
    for (점 p가 아닌 각 점 v에 대하여)
    {
      if (p와 v를 잇는 선분이 있으면)
        D[v] = 선분(p, v)의 가중치
      else
        D[v] = inf
    }
    Tree t = { p };
    while (t.size() < n)
    {
      트리 t에 속하지 않은 각 점 v들에 대하여, D[v]가 최소인 v_min을 선분과 함께 t에 추가한다.
      for (트리 t에 속하지 않은 각 점 w에 대하여)
      {
        D[w] = min(선분(v_min, w)의 가중치, D[w]);
      }
    }
    return t;
  }

  

  ---

시간복잡도

• while 루프가 (n - 1)번 반복되고, 각 루프 내에서 D[v]가 최소인 점 v_min을 찾을 때 O(n) 시간이 걸리므로 시간복잡도는 O(n²)이다.

  • 단, 배열 D를 힙 자료구조로 구현하면 시간 복잡도는 O(mlogn)이 될 수 있다고 한다.

---

크러스컬과 프림 알고리즘 비교

• 크러스컬 알고리즘에서는 선분이 하나씩 트리에 추가되는데, 이는 n개의 점들이 각각의 트리인 상태에서 점점 하나의 트리로 합쳐지는 것과 같다.

  • 즉 n개의 트리들이 점차 합쳐져서 1개의 신장 트리를 구성한다.

• 프림 알고리즘에서는 점 1개인 트리에서 시작되어 선분을 하나씩 추가시킨다.

  • 즉 1개의 트리가 자라나서 신장 트리가 된다.