Logseq/pages/크루스칼 알고리즘(Kruskal’s Algorithm).md

deck:: Logseq/coding tip

• 1. 개념(Concept)

  • 최소 스패닝 트리(MST)를 구하는 알고리즘.
  • “가장 가벼운 간선부터 선택하되, 사이클이 생기지 않게 한다.” 라는 그리디(Greedy) 전략을 사용.
    • 이를 위해 {{cloze 분리집합}}을 사용함. extra:: 분리집합(Disjoint Set) (Union Find) id:: 6950f5ad-52f1-4df3-b495-cbfa7a6ebbec

• 2. 동작 원리 (Algorithm Flow)

  • 1. 그래프의 모든 간선을 {{cloze 가중치 오름차순}} 으로 정렬한다. id:: 6950f5f7-a85f-49a9-96c1-a06afc1af444
  • 2. 가장 가중치가 낮은 간선부터 하나씩 꺼낸다.
  • 3. 선택한 간선이 연결하는 두 정점이 이미 같은 집합에 속해 있는지 확인한다.
    • 같은 집합이 아니라면 :-> 간선을 선택하고 두 집합을 합친다(Union) id:: 6950f9c6-8c02-4f9f-b860-bc9f2e768155
    • 같은 집합이라면 :-> 연결하면 사이클이 발생하므로 다음으로 넘어간다. id:: 6950f9d9-10e3-475d-8aec-aea39babab16
  • 3. 최종적으로 간선이 {{cloze V-1 (정점갯수 - 1)}} 개 선택되면 종료한다. id:: 6950f9ec-f8cb-4376-8505-3de0f465da7b

• 3. 코드(python)

  • 입력이 V(정점의 갯수), 모든 간선들의 집합(edges)을 매개변수로 하여 id:: 69510a18-7a5f-4a41-8113-f294b8263a21 크루스칼 알고리즘으로 최소 스패닝 트리를 구현하고, 이때 총 가중치를 반환하는 함수를 구현하면?

    # edges: (cost, a, b) 형태의 간선 리스트
    # parent: Union-Find용 부모 테이블이고 이미 자기 자신으로 초기회되어 있음.
    # union-find 연산은 이미 구현되어 있다고 가정
    

    #card

    • def kruskal(v, edges):
          edges.sort() # 1. 가중치 순 정렬
      
          total_cost = 0
          edge_count = 0
      
          for cost, a, b in edges:
              # 2. 사이클이 발생하지 않는 경우에만 선택
              if find(a) != find(b):
                  union(a, b)
                  total_cost += cost
                  edge_count += 1
                  if edge_count == v - 1: # 3. 간선 V-1개 모으면 종료
                      break
      
          return total_cost
      

• 4. 시간복잡도

  • 간선들을 정렬하고 그 간선들을 하나하나 탐색하기 때문에 간선의 정렬 시간이 가장 지배적임.
  • 시간복잡도는 {{cloze $O(E\log E)$}} id:: 69511394-6c6e-4da0-97e6-27c56fc37c71