[APS] 17. Kruskal 알고리즘 파이썬(Python)으로 구현하기

저번에 Prim 알고리즘을 포스팅 하면서, 최소신장트리(MST)에 대해서 작성한 적이 있었다.

Kruskal도 Prim과 마찬가지로 MST를 구하는 다른 방법에 해당한다.

• 신장트리

  : n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

• MST (Minimum Spanning Tree)

  : 신장트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

---

1. Kruskal 알고리즘이란?

• Prim 알고리즘을 간단하게 복습해보자면, 임의의 점을 골라서 시작한다 .
  1. key값이 최소인 점을 탐색한다
  2. 그 점으로부터 도달할 수 있는 지점에 대한 최소 key값을 갱신한다.

     → 모든 지점을 방문할 때까지 1. 2.를 반복한다.

• Prim 알고리즘을 공부하다 보면, 이런 생각이 들 수도 있다.

💡

그냥 가중치가 제일 낮은 간선부터, DP 하듯이 연결 하면 안되나요?

이 아이디어를 사용한 것이 Kruskal 알고리즘이라고 할 수 있겠다.

처음부터 각 간선의 가중치를 적은 것부터 정렬해서 사용한다.

단, 선분이 cycle(1바퀴를 돌아 자신으로 돌아오는 것)을 이루지 않게 확인하면서 진행하면 된다.

2. 앗.. 그러면 cycle 검사를 어떻게 하죠?

• 그래서 이 전에 포스팅한 상호배타집합 을 사용한다.

• 상배집? 그게 뭔데요 하는 사람은 이전 포스팅을 먼저 읽고 오도록 한다.

3. Kruskal 알고리즘, 파이썬으로 구현해보기!

• 최종적인 진행 순서는 다음과 같다.
  1. 간선의 가중치가 가장 낮은 것 부터 정렬한다.
  2. 시작점, 끝점에 대해서 find_set (대표자 찾기) 를 진행한다.

     ⇒ 대표가 같으면, cycle 을 이루는 것이기 때문에 선택하지 않는다.

     ⇒ 대표가 같지 않으면, 같은 집합으로 취급하기 위해 union 을 진행한다.

  3. 모든 점을 잇는 간선을 선택할 때까지 진행한다.

• python 으로 최종작성한 코드는 다음과 같다.

  cf ) union() 과 find_set() 함수는 이전 포스팅을 참고하길 바란다.

  V, E = map(int, input().split())
  
  
  adj = []
  for _ in range(E):
      n1, n2, w = map(int, input().split())
      adj.append((n1, n2, w))
  
  adj.sort(key=lambda x:x[2])
  weight = 0
  cnt = 0
  
  p = [ i for i in range (V+1)]
  
  while True:
      if cnt == V: # 최소 간선의 개수만큼 골랐다면 종료한다.
          break
  
      s, e, w = adj.pop(0)
      # 시작점과 종료지점에 대해서 대표가 같다면, continue
      if find_set(s) == find_set(e):
          continue
  
      else:
          cnt += 1
          union(s,e)
          weight += w

Uploaded by N2T