5.2 최소 신장 알고리즘

최소 신장 트리(MST)

: 가중치가 있는 그래프에서 간선의 가중치 총합이 가장 작은 신장 트리

 

1. 프림 알고리즘

: 임의의 정점을 시작점으로 트리를 확장하면서 최소 신장 트리를 생성 -> 가중치가 가장 작은 간선으로 연결된 정점을 트리에 추가하면서 최소 신장 트리를 생성

 

 

2. 크루스칼 알고리즘

: 간선을 오름차순으로 정렬한 뒤 가중치가 낮은 간선을 선택하면서 최소 신장 트리를 생성하는 방식 -> 가중치의 오름차순으로 간선을 정렬하는 알고리즘과, 사이클의 생성 여부를 판단하는 union-find 알고리즘을 함께 사용함

흩어져 있는 여러 트리(노드)를 가중치가 작은 간선으로 연결해 하나의 최소 신장 트리를 생성