최소 신장 트리(Minimum Spanning Tree)

그래프에서 최소 비용을 구하는 문제

1. 모든 정점을 연결하는 간선들의 가중치합이 최소가 되는 트리 - 프림과 크루스칼 두가지 형태가 있다.

(프림은 정점을 기준으로, 크루스칼은 간선을 기준으로 MST를 만들어간다.)

2. 두 정점 사이의 최소 비용 경로 찾기  - BFS에서 가중치가 추가된 형태

 

신장 트리

1. n 개의 정점으로 이루어진 무방향 그래프에서 n 개의 정점과 n-1 개의 간선으로 이루어진 트리

 

최소 신장 트리

1. 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

 

 

그래프의 표현

1. 인접 행렬

인접 행렬

2. 인접 리스트

인접 리스트

🟨 프림 알고리즘:

프림 알고리즘은 하나의 정점에 연결된 간선중 가중치가 최소인 정점을 선택한다.

 

하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 알고리즘

1. 임의로 노드를 하나 선택하고 시작한다.

2. 선택한 노드와 인접하는 노드들 중 최소 가중치의 간선과 연결된 노드를 선택

3. 모든 노드가 선택될 때까지 위의 과정을 반복한다.

 

MST 리스트

MST에 포함되는 노드들과 그렇지 않은 노드들로 나누어 관리한다.

(보통 알고리즘을 풀 때 visited리스트와 비슷한 개념이라고 생각하면 된다)

 

🟦 이 알고리즘으로 해결한 문제:

https://deok2kim.tistory.com/67

[python] SWEA - 1251. [S/W 문제해결 응용] 4일차 - 하나로