출처 : 동빈나 크루스칼 알고리즘

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

• 가장 적은 비용으로 모든 노드 연결 = 최소 비용 신장 트리를 만들기 위한 대표 알고리즘
• 여러 도시가 있을 때 각 도시 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자 할 때 실제로 적용되는 알고리즈

용어 정리

• 노드 = 정점 = 도시 : 그래프에서 동그라미에 해당
  = 간선 = 거리= 비용 : 그래프에서 선에 해당

아래 그래프에서의 노드 갯수 : 7개, 간선 갯수 : 11개!
업로드중..

크루스칼 알고리즘 핵심 : 간선을 거리가 짧은 순서대로 그래프에 포함

• 모든 노드를 최대한 적은 비용으로 '연결만' 시키면 되기 때문에 모든 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근히 그래프에 포함시키면 됌
  

• 노드 1부터 노드 7까지 연결된 모든 간선 정보를 저장한 것

• 노드 6,7은 간선정보 없는데 이유는 이미 다른 노드들의 간선 정보에 모두 포함 되어 있기 때문임

• 간선이 총 11개 존재
  

• 위와 같이 모든 간선을 '거리(비용)'을 기준으로 오름차순 정렬

• 이제 다음 알고리즘에 맞게 그래프 연결하면 가장 적은 비용으로 모든 노드 연결한 그래프인 '최소 신장 트리' 완성

1. 정렬된 순서에 맞게 그래프에 포함
2. 포함시키기 전에는 사이클 테이블 확인
3. 사이클을 형성하는 경우 간선에서 제외

사이클

• 그래프가 서로 연결되어 사이클을 형성

• 최소 비용 신장 트리에서는 사이클이 발생하면 안됌
  

• 사이클 발생하는 여부는 지난 시간 : Union-Find알고리즘을 그대로 적용하면 됌