최소 신장 트리 Minimum Spanning Tree, 크루스칼 Kruskal's, 프림 Prim's 알고리즘

Greedy Algorithm

• 각 단계에서의 최선책을 선택하여 다음 단계로 진행하는 알고리즘
• 현재 선택에 의해 다음 단계의 조건이 변하는 경우 부적합

---

최소 신장 트리 MST

• 모든 노드를 포함하는 그래프, 모든 노드가 연결된 그래프, 트리 속성을 만족하는 그래프
• 그래프 상에서 각 간선에 가중치가 부여됨
• 한 정점을 기준으로 가능한 가장 작은 가중치의 간선들을 사용하여 모든 정점을 연결하는 트리(MST)
• MST를 구하는 문제를 푸는 알고리즘

  1. 크루스칼

     가장 작은 값의 간선을 선택한다.

     → 그 다음 작은 값의 간선을 선택한다.

     → 그 다음으로 작은 값의 간선을 선택하되 사이클이 생기지 않게 선택한다.

     → 모든 정점을 선택할 때까지 위 선택 과정을 반복한다.

  2. 프림 알고리즘

     기준 정점에서 출발하는 가장 작은 값은 간선과 그 간선을 통해 도착하는 정점을 선택한다.

     → 선택된 정점들에서 출발하고, 아직 선택되지 않은 간선 중 가장 값이 작은 간선과 그 간선을 통해 도착하는 정점을 선택한다.

     → 모든 정점을 선택할 때까지 위 선택 과정을 반복한다.

     ** 계속해서 가장 작은 가중치의 간선 즉, 최선의 선택을 하기 때문에 그리디 알고리즘의 일종이다.

---

Disjoint Set 

• 서로 중복되지 않는 부분 집합으로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조

• Set : 순서를 고려하지 않는 개체들의 집합

• subset superset

  set A ⊂ set B

  A는 B의 부분집합, B는 A의 초월집합

• partition : 각 부분집합 set을 쪼개는 것

  • 쪼개진 부분집합을 합치면 원래로 돌아간다.

  • 쪼개진 부분집합끼리는 교집합되는 원소가 없다.

• operations

  • make-set(x) : x를 유일한 원소로 하는 새로운 셋을 만든다.

  • union(x,y) : x가 속한 셋과 y가 속한 셋을 합친다.

  • find(x) : x가 속한 셋의 루트노드 값을 반환한다.

---

크루스칼 알고리즘 Kruskal's algorithm

• 분석 대상 노드에 연결된 엣지 중 가중치가 최소인 엣지를 고르면서 트리 속성을 깨지지 않도록 체크하는 방식

• light edge : 가중치가 최소인 엣지

• safe edge : 가중치가 최소는 아니지만 트리 속성을 만족하는 엣지

• Disjoint set 을 기본 자료구조로 활용

• process
  1. 모든 노드에 대해 make-set 연산 수행
  2. 모든 엣지를 가중치를 기준으로 오름차순 정렬
  3. 가중치가 가장 작은 엣지부터 시작
  4. 분석 대상 엣지의 노드들이 서로 다른 셋이기 때문에 safe한 엣지임을 find operation을 통해 확인
  5. 각 노드가 속한 셋을 union
  6. 그 다음으로 가중치가 작은 엣지도 같은 방식 수행하여 계속 safe한 엣지에 붙은 노드들을 같은 셋에 포함시키다가 같은 셋에 있는 노드들이 이웃한 엣지를 만나면 트리 속성을 위배(사이클 존재)하기 때문에 건너 뛴다.
  7. 위와 같은 방식으로 모든 엣지에 대한 분석을 마치면 종료
• algorithm
  • 사이클이 생기면 트리 속성 위배 -> 해당 헷지는 스킵하고 다음 작은 가중치 엣지로 넘어감

KRUSKAL(V, E, w)
1. A <- ∅
2. for each vertex v ∈ V
	do MAKE_SET(v)
3. sort E into nondecreasing order by weight w
4. for each (u,v) taken from the sorted list
	do if FiND_SET(u) != FIND_SET(v)
    	then A <- A ∪ {(u,v)}
        	UNION(u,v)
5. return A

• 시간 복잡도 : O(ElogE)

---

Prim's Algorithm 프림 알고리즘 

• process
  • solution set과 non-solution set사이를 연결하는 엣지 가운데 가장 가중치가 작은 엣지를 뽑고 해당 엣지에 연결된 노드와 엣지를 solution set에 넣는다.
  • solution set에 모든 노드가 포함되면 알고리즘 종료

1. 시작 노드에 연결된 엣지중 가중치가 가장 작은 엣지 선택
2. 해당 엣지에 연결된 노드와 해당 엣지를 solution set으로 포함
3. 이미 포함된 노드들을 포함하는 엣지는 가중치가 가장 작더라도 배제
4. 모든 노드가 선택되었으면 종료

• algorithm

• 시간복잡도 : O(ElogV)

 

---

References

• 성균관대학교 소프트웨어학과 조대호 교수님 2020년도 2학기 알고리즘 수업