WEEK03- TIL 최소 스패닝 트리

최소 신장(스패닝) 트리 (minimum spanning tree)

= 전체 요소들을 연결할 때 사용한다. kruskal 알고리즘, prim 알고리즘이 있다.

 

스패닝 트리란?

- 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프

 

조건?

- 본래의 그래프의 모든 노드를 포함해야 함

- 모든 노드가 서로 연결

- 트리의 속성을 만족시킴(사이클이 존재하지 않음)

☞ 사이클이란?

 그래프가 서로 연결되어 사이클을 형성하는 경우. 최소 비용 스패닝 트리에서는 사이클이 발생하면 안 된다!

 애초에 모든 노드를 이어붙이기만 하면 되는데 사이클이 발생할 이유가 없다고 한다!

==> 이러면 안됩니다~

 

크루스칼 kruskal

1. 간선들을 정렬

2. 간선이 잇는 두 정점의 root 찾기

3. 다르면 하나의 root를 바꾸어 연결 시킴

 

프림 prim

1. 임의의 정점을 선택

2. 해당 정점에서 갈 수 있는 간선을 minheap에 넣음

3. 최소값을 뽑아 해당 정점을 방문 안 했으면 선택

 

​크루스칼 알고리즘은 간선들을 정렬해야하기 때문에 간선이 적다면 크루스칼로, 많다면 프림으로 사용한다.

→ 근데 크루스칼을 더 사용 많이 한다고..!