크루스칼1 크루스칼(Kruskal)과 프림(Prim) 알고리즘 신장 트리(Spanning Tree) 그래프의 모든 정점을 연결한 트리를 말한다. 사이클이 생기지 않는 선에서 간선의 개수를 (정점 개수 - 1)개로 만드는 것으로, 하나의 그래프에서 신장 트리는 여러 형태가 나올 수 있다. 최소 신장 트리(MST; Minimum Spanning Tree) 신장 트리 중에서 간선들의 가중치 합이 최소인 트리를 말한다. 최소 신장 트리는 다음과 같은 조건을 만족한다. 1. 간선의 가중치 합이 최소이다. 2. 사이클이 없다. 3. 모든 정점이 연결되어 있으며, (정점 개수 -1)개의 간선을 가지는 트리이다. 4. 무방향 가중치 그래프이다. 도로망, 통신망, 유통망 등 비용을 최소로 해야 하는 경우, 즉 MST를 구할 때 프림 알고리즘, 크루스칼 알고리즘을 사용한다. 크루스칼.. 2021. 10. 2. 이전 1 다음
