알고리즘 7 그래프_2

최소 신장 트리 (Minimum Spanning Tree)

- 그래프에서, 루프를 형성하는 간선만 제거하면 트리가 됨 

- 각 구성 요소가 서로 연결되어 있고, 간선에 가중치가 실려 있는 연결된 가중치 그래프 

 

최소 신장 트리 만드는 알고리즘

- 프림 알고리즘

- 크루스칼 알고리즘 

 

프림 알고리즘 

- 그래프와 최소신장트리준비

- 임의의 정점을 시작 정점으로 -> 최소신장트리의 뿌리 노드로 삽입

- 정점의 간선 가중치를 조사 -> 가장 가중치가 작은 인접접점 -> 최소 신장트리에 삽입 

- 사이클이 생성되지 않도록 이를 반복 

- 모든접점 순회가 끝나면 종료  

- 우선순위 큐를 통해서, 정점 추가 시 마다, 조사 대상을 추가할 수 있음 

- Vertex를 조회하면서, Vertex 별 가장 웨이트가 낮은 간선 정보를 수집 

 

크루스칼 알고리즘 

- 간선을 가중치의 오름차순으로 정렬 (우선순위 큐 )

- 간선을 순회하면서 최소 신장 트리에 추가 -> 이 떄 사이클이 만들어지지 않게 함 

?? 어떻게 사이클 구성이 됬는지 안됬는지를 판별하는 가

-> 분리집합을 이용하여 판별 

-> 만약 두 개의 정점이 이미 같은 집합에 있다면 간선을 추가하지 않을 수 있음 

 

 

GitHub - Sukmin-LanternK/Algorithm