최소 신장트리

 

사이클을 만들면 안됨(트리이기 때문)

모든 노드가 연결 되어 있어야 함

 

 

 

 

 

 

 

 

 

Kruskal 알고리즘

• 간선을 가중치가 감소하지 않는 순서로 정렬(오름차순)
• 가장 가중치가 작은 간선을 트리에 추가하여 사이클을 만들지 않으면 트리 간선으로 선택
• 사이클을 만들면 버리는 것을 반복
• n-1개의 간선이 선택되면 알고리즘 종료
• Kruskal 알고리즘인 그리드인 이유 : 남아있는(정렬된) 간선들 중에서 항상 가중치가 작은 간선 선택

알고리즘 큰 흐름

 

예시

코드

weight

수행시간

요점

• 가장 가중치가 작은 값들의 간선부터 연결하고 만약에 연결했는데 사이클이 생기면 삭제하고 다른 간선을 사용
• 간선이 조밀(많은)한 경우 이것이 유리

 

Prim 알고리즘

• 임의의 시작 정점에서 가장 가까운 정점을 추가하여 간선이 하나의 트리를 만들고, 만들어진 트리에 인접한 가장 가까운 정점(가중치가 낮은)을 하나씩 추가하여 최소신장트리를 만듬
• 초기에 트리 T는 임의의 점점 s만을 가지며, 트리에 속하지 않은 각 장점과 T의 정점에 인접한 간선들 중에서 가장 작은 가중치를 가진 간선의 끝점을 찾기위해 리스트 D를 사용

알고리즘 큰 흐름

예시

코드

실행시간

요점

• 간선이 희소(적은) 경우 이것이 유리

Sollin 알고리즘

• 각 정점을 돌깁적인 트리로 간주
• 각 트리에 연결된 간선들 중에서 가장 작은 가중치를 가진 간선 선택
• 이때 선택된 간선은 정점2개를 1개의 트리로 만듬 (트리 2개를 합친다는거임)
• 같은 방법으로  하나의 트리가 남을 때까지 각 트리에서 최소 가중치 간선을 선택하여 연결
• 병렬 알고리즘으로 구현이 쉬움

알고리즘 큰 흐름

예시

코드

• 실행시간 Sollin 알고리즘에서 repeat-루프가 예제와 같이 각 쌍의 트리가 서로 연결된 간선을 선택하는 경우 최대 logN번 수행
• 루프 내에서는 각 트리가 자신에 닿아 있는 모든 간선들을 검사하여최소 가중치를 가진 간선을 선택하므로 O(M) 시간이 소요
• 따라서 알고리즘의 수행 시간은 O(MlogN)

요점