알고리즘 설명 크루스칼 알고리즘(Kruskal, 최소 신장 트리, MST) KQNG 2018. 7. 18. 11:49 이웃추가 본문 기타 기능 바로 전 포스트에서 최소 신장 트리를 구현하는 알고리즘인 프림 알고리즘에 이어서 다른 알고리즘인 크루스칼 알고리즘에 대해 간략히 설명해보도록 하겠습니다. 프림알고리즘은 정점을 중심으로 진행해나간다 하였는데 크루스칼 알고리즘은 간선을 중심으로 진행해가는 알고리즘입니다.
다음과 같이 정점들과 각 정점들을 있는 간선의 비용이 주어지면 크루스칼 알고리즘의 진행 과정은 다음과 같습니다. (a) 간선 중 가장 비용이 적은 1을 선택해 1번과 2번 정점을 이어줍니다.
(b) 다음 간선 중 가장 비용이 적은 2를 선택해 1번과 3번 정점을 이어줍니다. (c) 다음 간선 중 가장 비용이 적은 3을 선택해 2번과 3번 정점을 이어주려합니다.
그러나 2번과 3번을 이으면 1번 2번 3번 3개의 점이 사이클을 이루기 때문에 그려줄 수 없습니다. 따라서 이어주지 않...
#
Kruskal
#
크루스칼
#
코딩
#
최소신장트리
#
최소스패닝트리
#
자료구조
#
알고리즘
#
백준
#
MST
#
프로그래밍
![[전문연구요원 훈련소 후기(3주)] - 3주차 + 후기](https://blogimgs.pstatic.net/nblog/mylog/post/og_default_image_160610.png)