728x90 반응형 greedy algorithm1 [Algorithm] MST - 크루스칼 알고리즘(Kruskal Algorithm) 개요 ◎ 크루스칼 알고리즘이란? ◎ 그림 예시 ◎ 구현 코드 (Java) ◎ 시간 복잡도 ◎ 특징 안녕하세요. J4J입니다. 이번 포스팅은 크루스칼 알고리즘에 대해 적어보는 시간을 가져보려고 합니다. 크루스칼 알고리즘이란? 크루스칼 알고리즘은 대표적인 MST 구현 알고리즘 중 하나로 정점들 간의 연결된 길(간선)의 가중치를 작은 순서대로 선택하며 MST를 만드는 기법입니다. 예를 들어 A, B, C, D, E 정점이 있다고 가정해보겠습니다. A ↔ C 가중치: 3 A ↔ D 가중치: 5 B ↔ C 가중치: 4 B ↔ D 가중치: 4 C ↔ E 가중치: 2 D ↔ E 가중치: 1 일때 다음과 같은 순서로 가중치를 선택합니다. 1-1. 가중치가 1로 가장 작은 D ↔ E 간선을 임의로 선택합니다. 1-2. .. 2021. 1. 30. 이전 1 다음 728x90 반응형
