Kruskal's Algorithm

• Minimum Spanning Tree (MST) - 최소 신장 트리
• 간선 기준
  • 전체 관점시점으로 접근
    • 모든 간선에서 최소를 아니까
  • 로직
    • 간선 거리별로 정렬
      • sort
    • 작은 거리부터 포함 - Greedy
      • 단 사이클이 발생하지 않을때 포함(집합) - Union-Find
      • 누적하려는 최소 거리의 노드가 이미 같은 부모(집합)라면 사이클 이므로 pass
    • 노드 - 1 개의 간선이 포함되면 종료 or 간선 다 순회
      • 정렬된 간선을 다 돌면 종료
  • 초기 값
    • 정렬된 간선
    • 모든 노드에 대해서 rank[x] = 0, parent[x] = x 인 union-find용 자료
    • 정렬된 간선 완전 탐색 for
  • $E\log E$
    • 정렬에서 가장 최악