신장트리 (1) 썸네일형 리스트형 [알고리즘] MCST - Kruskal's Algorithm (크루스칼 알고리즘) Spanning Tree (신장 트리) Graph의 모든 Vertex를 포함하는 Sub Graph이자 Tree 모든 정점들이 연결되어 있어야 한다. 사이클이 없어야 한다. (트리니까) Edge의 개수는 N-1개이다. (N: Node의 수) MCST (최소 비용 신장 트리) Minimun Cost Spanning Tree Graph의 신장 트리 중 Edge의 가중치 합이 최소인 신장 트리 MCST - Kruskal's Algorithm 1. Edge들을 가중치 기준으로 오름차순 정렬 (가중치 작은 거 -> 큰 거) 2. 가중치가 작은 Edge들부터 시작하여 다음을 반복 1) 선택된 Edge의 양 끝 Node들이 속한 집합을 확인한다. (Find) 2) 같은 집합에 속하지 않다면 : 두 Node가 속한 집합.. 이전 1 다음
