MST1 [알고리즘] 최소 비용 신장 트리(MST) - 크루스칼 알고리즘(Kruskal Algorithm) 신장 트리 (Spanning Tree) 신장 트리란 그래프안에서 모든 정점(노드)을 포함하는 트리이다. 신장 트리는 모든 정점들이 연결되어 있어야 하고, 사이클을 포함하면 안된다. (사이클: 그래프가 순환되어 돌아오는 경로) 신장 트리는 그래프에 있는 n개의 정점을 n-1개의 간선으로 연결하게 된다. 최소 비용 신장 트리 MST (Minimun Spanning Tree) 신장 트리들 중에서 사용된 간선의 가중치 합이 최소인 트리를 말한다. 크루스칼(Kruskal) 알고리즘과 프림 알고리즘이 있다. 크루스칼 알고리즘(Kruskal Algorithm) 그리디 알고리즘을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하여 최적의 답을 구하는 알고리즘이다. 크루스칼 알고리즘 동작 그래프의 간선들을 가중치의 오.. 2021. 11. 10. 이전 1 다음
