목록kruskal (1)

유블로그

[알고리즘] 최소 신장 트리(MST) - KRUSKAL 알고리즘

그래프에서 최소 비용 문제 모든 정점 연결 간선들 가중치 합이 최소가 되는 트리 두 정점 사이 최소 비용 경로 찾기 신장 트리 : n개 정점 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리(Minimum Spanning Tree) : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 : 서로소 집합 사용 간선을 하나씩 선택해서 MST 를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬(최대신장트리는 내림차순) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 - 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택(union 연산 실패 상황) n-1 개의 간선이 선택될 때까지 2를 반복 ..
알고리즘 2020. 8. 6. 10:23
이전 Prev 1 Next 다음