목록path compression (1)

포시코딩

[MST][최소 신장 트리] Kruskal's algorithm

크루스칼 알고리즘(Kruskal's algorithm) 탐욕 알고리즘을 기반으로 한다. 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 비용(가중치)을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (사이클이 생기지 않도록) 간단히 말해서, 모든 정점을 리스트로 만든 후 비용이 적은 간선부터 하나씩 연결하되 사이클이 생기지 않게 하면 된다. 언제까지? 모든 노드들이 연결될 때까지 과정 아래와 같은 그래프가 있다고 가정할 때, 크루스칼 알고리즘으로 최소 신장 트리를 구하는 과정에 대해 알아보자 1. 가장 가중치가 작은 간선은 5의 가중치를 가진 A-D, C-E가 있다. 뭘 먼저 선택하든 상관없지만 우선 A..
자료구조알고리즘/이론 2023. 4. 18. 06:05
이전 Prev 1 Next 다음