프림 알고리즘

크루스칼 알고리즘

3가지 성질

1. 트리의 성질

• n개의 노드 , n-1 개의 에지
• 에지 삭제 ⇒ 2개의 서브트리로 분할됨
• 새로운 에지 삽입 ⇒ 에지를 포함한 사이클이 생성됨

1. Cut property ⇒ 프림 알고리즘 (노드 기준)

• 2개의 서브 트리로 나눌 수 있는 에지들의 집합
• cut 에서 최소(비용)에지를 포함하는 MST는 최소 하나 이상 존재한다.

1. Cycle property ⇒ 크루스칼 알고리즘 (엣지 기준)

• 임의의 cycle 의 최대 비용 에지를 포함한 MST는 없다.