최소신장트리1

• 

  최소 신장 트리(MST) : 크루스칼(Kruskal) & 프림(Prim) 최소 신장 트리최소 신장 트리를 구하라라는 문장을 코딩테스트를 하면 많이 볼 수 있다.이 문장의 뜻은 간선에 비용이 있는 그래프에서 간선을 선택하여 모든 정점을 연결하였을 때, 비용의 합이 최소가 되도록 함을 의미한다.- 각 시점에서 최선의 선택을 하는 알고리즘인 그리디(Greedy) 알고리즘 부류입니다. 신장트리- 모든 정점을 연결하는 간선의 집합. 크루스칼(Kruskal) 알고리즘- 크루스칼을 이용하여 최소 신장 트리를 구하는 방법은 다음과 같습니다. 1) 간선을 오름차순으로 정렬한 다음2) 간선 하나씩 선택하며 폐로(사이클)이 생기는지 확인한 뒤,3) 생기지 않으면 간선 리스트에 추가를, 생기면 간선 리스트에 접근 금지를 한다.반복하다보면 모든 정점이 연결될 것입니다. ex) 최소 신장 트리를 만들.. CS 지식/자료구조_알고리즘 2025. 1. 15.