Algorithm/알고리즘 개념
[알고리즘] 최소 신장 트리 - Prim, Kruskal Algorithm(프림, 크루스칼 알고리즘)
최소 신장 트리(Minimum Spanning Tree)란? 💡최소 신장 트리: 그래프에서 모든 정점에 대해 최소한의 연결만을 남긴 그래프이다. 즉 간선의 가중치 합이 가장 작은 트리를 뜻한다. 사이클이 존재하지 않아야 한다. 최소 신장 트리를 찾는 알고리즘으론 크루스칼 알고리즘, 프림 알고리즘이 있다. 이 알고리즘은 그리디 알고리즘 기법을 활용한 알고리즘이다. 프림 알고리즘은 바이너리 힙을 이용하는 경우 O(E+VlogV)의 시간 복잡도를 가지며, 크루스칼 알고리즘은 경로 최적화를 이용하지 않는 경우 O(ElogV), 경로 최적화를 이용하는 경우 O(Elog∗V)의 시간 복잡도를 가지기 때문에, 그래프의 간선 밀도를 고려하여 최적의 알고리즘을 선택하는 것이 필요하다. 크루스칼 알고리즘(Kruskal A..
