최소 신장 트리(MST)

Spanning? 신장?

1. 정의와 성질

1.1 신장 트리

우측 그래프들이 좌측 그래프의 신장 트리

원래 그래프의 모든 노드를 포함하면서 사이클이 없는, 즉 단순 연결 그래프인 부분 그래프를 의미한다.

• 모든 노드 포함(V-1개의 edge)
• 사이클 없는

1.2 최소 신장 트리

신장 트리 중에서 가중치의 합이 최소인 트리를 의미. 여러개일 수 있다.

2. 크루스칼 알고리즘

유니온 파인드를 알고있어야 이거랑 프림까지 잘 할수있다.

3. 프림 알고리즘