12일차 강의 (27강)

최소 신장 트리(MST) (27강)

부분그래프

→ 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 그래프를 의미

신장트리

→  주어진 방향성이 없는 그래프의 부분 그래프들 에서 모든 정점을 포함하는 트리를 의미

 최소신장트리

→ 신장 트리중에서 간선의 합이 최소인 트리를 의미

 

크루스칼 알고리즘 (유니온 파인드 알고리즘 이용)

1. 간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택

2. 현재 선택한 간선이 정점 u, v를 연결하는 간선이라고 할 때 만약 u와 v가 같은 그룹이라면 아무 것도 하지 않고 넘어감, u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가

3. 최소 신장 트리에 V-1개의 간선을 추가시켰다면 과정을 종료, 그렇지 않다면 그 다음으로 비용이 작은 간선을 선택한 후 2번 과정을 반복 

 

프림 알고리즘

1. 임의의 정점을 선택해 최소 신장 트리에 추가

2. 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가

3. 최소 신장 트리에 V-1개의 간선이 추가될 때 까지 2번 과정을 반복

→

1. 임의의 정점을 선택해 최소 신장 트리에 추가, 해당 정점과 연결된 모든 간선을 우선순위 큐에 추가

2. 우선순위 큐에서 비용이 가장 작은 간선을 선택

3. 만약 해당 간선이 최소 신장 트리에 포함된 두 정점을 연결한다면 아무 것도 하지 않고 넘어감,

해당 간선이 최소 신장 트리에 포함된 정점 u와 포함되지 않은 정점 v를 연결한다면 해당 간선과 정점 v를 최소 신장 트리에 추가 후 정점 v와 최소 신장 트리에 포함되지 않는 정점을 연결하는 모든 간선을 우선순위 큐에 추가

4. 최소 신장 트리에 V-1개의 간선이 추가될 때 까지 2, 3번 과정을 반복

 

+ 가중치의 합만을 필요한 경우엔 pq에 (비용, 정점2)만 담은 pair<int, int>로도 해결이 가능하다.