최소 신장 트리1 TIL : Kruskal(크루스칼) 알고리즘 (9) 💻 알고리즘 📌 크루스칼 알고리즘 프림 알고리즘과 같이 대표적인 최소 신장 트리(MST)를 찾는 알고리즘이다. 이 알고리즘의 특징과 동작 원리는 다음과 같다. ✔️ 특징 확인하는 그래프가 무방향 그래프이고 가중치가 존재한다. 가장 비용이 작은 것부터 확인하기 때문에 그리디 알고리즘의 일종이다. 순환(Cycle)이 있는지 확인하기 위해서 Union-Find 알고리즘을 사용한다. ✔️ 동작 원리 입력받은 간선들을 cost을 기준으로 정렬한다. 가장 작은 비용을 가진 간선을 확인한다. 사이클이 안 만들어지면 추가하고 만들어지면 다음 간선을 확인한다. 간선의 개수가 정점 - 1 개가 될 때까지 반복한다. # find function def find(x): if x != parent[x]: parent[x] = .. 2022. 8. 21. 이전 1 다음