크루스칼 알고리즘 (Kruskal Algorithm)

👉 크루스칼 알고리즘은 MST(최소 스패닝 트리) 찾는 알고리즘들 중 하나입니다. (나머지 하나는 Prim 알고리즘) 💡 MST란? 그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제 크루스칼 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 가는 방식으로 동작합니다. 하지만, 가중치가 작다고 해서 무조건 간선을 트리에 더하는 것이 아닌, 사이클이 생기는 간선을 고려해 제외 해줍니다. 👉 동작하는 과정 위 그래프를 보면 가중치가 1인 간선, 2인 간선, 3.. 순서대로 선택해 가고 있습니다. 이때 4번째에서 5번째를 보면 가중치가 3인 간선들이 남아 있는데도 불구하고, 4인 (c,d) 간선이 추가됩니다. 그 이유는 3인 간선들이 추가되면 트리..