크루스칼 알고리즘

• 신장 트리
  • 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미.
  • 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 함.

 

• 최소 신장 트리
  • 최소한의 비용으로 구성되는 신장 트리

 

• 크루스칼 알고리즘  
  • 최소 비용 신장 트리를 찾는 알고리즘
  • Edge의 개수를 E, Vertex의 개수를 V라고 하면 이 알고리즘은 O(ElogV)의 시간복잡도를 갖는다.
  • 구체적인 동작 과정 
    • 간선 데이터를 비용에 따라 오름차순으로 정렬
    • 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
      • 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
      • 사이클이 발생하는 경우 최소 신장 트리에 포함 X
    • 모든 간선에 대하여 2번의 과정을 반복

 

[참고] 

ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 

www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8