Notice
Recent Posts
Recent Comments
Link
«   2024/12   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
Tags more
Archives
Today
Total
관리 메뉴

목록크루스칼 알고리즘 (1)

기억을 위한 기록들

[알고리즘]크루스칼 알고리즘(Kruskal's Algorithm)

그래프 내의 모든 간선들의 가중치 정보를 사전에 파악하고 이 정보를 토대로 최소 신장 트리를 구축해나가는 것이 특징입니다. 작동 순서 1. 그래프 내의 몯느 간선을 가중치의 오름차순으로 목록을 만듭니다. 2. 1번에서 만든 간선의 목록을 차례대로 순회하면서 간선을 최소 신장 트리에 추가합니다. 단, 이때 추가 된 간선으로 인해 최소 신장 트리 내에 사이클이 형성되면 안됩니다. 해결해야 할 문제 최소 신장 트리에 생기는 사이클을 어떻게 효율적으로 감지 할 것인가? 대안 각 정점들을 각각의 집합 안에 입력하고, 간선으로 연결되어 있는 정점들에 대해서는 합집합을 수행. 이때 간선으로 연결할 두 정점이 같은 집합에 속해 있다면 이 연결은 사이클을 이루게 됨. 예제 사이클 탐지의 문제를 해결 했으니 예제를 통해 ..
자 & 알/알고리즘 2021. 1. 27. 17:38
이전 Prev 1 Next 다음