[알고리즘] 크루스칼(Kruskal) 알고리즘 파이썬, 최소신장트리(MST), union-find기법(union-by-rank, path-compression)

 

# 설명

## 최소신장트리

그래프나 트리 내에서 최소신장트리를 찾을때 사용되는 알고리즘이다. 최소 신장트리(MST)는 그래프상의 모드 노드가 연결된 상태이면서 사이클(순환)구조가 없는 경우를 뜻 한다.

출처 https://ratsgo.github.io/data%20structure&algorithm/2017/11/28/MST/

 

## union-find 기법

 결국 순환구조를 찾기 위해서는 어떠한 방법이 필요한데, 그때 이용되는 방법이 union-find기법이다. 각각의 노드들이 간선이 연결됨에 따라서 하나의 부분집합으로 생각한다. 즉 초기에는 (1), (2), (3), (4), (5,) (6)의 부분집하들이 존재하고, (1,2),(3,4),(5,6)와 같이 정점이 연결됨에 따라서 부분집합으로 표기하는 방법이다. 순환구조가 생긴다는 것은 집합내에 같은 원소가 존재해버리는 경우다, 예를 들어 (1,2,3)과 (3,4,5)의 두개의 그래프를 합치기위해 집합을 비교해보면 3이 중복된다. 이 경우 합치면 사이클이 생긴다는 뜻이다. 

 집합을 구성할때 하나의 leaf->parent->parent->root와 같은 형태로 구성하고, 이 두개의 집합을 합칠때(union) 최상의 root가 같으면 사이클이 존재해버린다느 뜻이다. 

### union by rank

 아무 생각없이 union을 하게 되면 worst 케이스가 생길 수 있다. 

그렇기 때문에 두 그래프를 합치기 전에 각 그래프의 rank(높이)를 살핀 후, 작은 rank를 가진

그래프가 큰 rank를 가진 그래프의 root노드에 붙게 설계하여 그래프가 평평하게 유지 될 수 있도록 해야 한다.

 

### path-compression

 한번 find를 하게 되면 find노드의 parent들의 root가 뭔지 알게 된다. 그럴 경우 parent를 root로 바꿔주게 되면 다음번에 find할 시에 한번에 찾을 수 있다.

 

## 크루스칼 알고리즘

 탐욕알고리즘과 유사하게, 모든 간선(edge)를 가장 낮은 weight로 정렬시킨 후, 가장 낮은 엣지를 선택한다. 두 노드는 선택된 엣지에 의해서 이어지게 된다. 간선을 선택하기전에 간선을 추가하면 사이클이 형성되는지 확인 한 후 그렇지 않을 경우에만 엣지를 확정 짓는다.

 모든 노드가 선택되면 MST가 구현된다.

 

 

# 사용된 그래프

# 코드

"""
  MST (최소신장트리)를 구하는 알고리즘
  탐욕알고리즘과 유사하게 가장 작은 엣지를 순차적으로 선택
  선택된 엣지에 사이클이 존재하는 경우는 pass
  사이클이 생성되는 유무를 확인하기 위해서 union-find 기법을 사용
  union-by-rank 기법을 활용하여 각 트리의 대한 높이를 기억하여 합칠때 사용
  path-compression 를 사용하여 한번 find를 실행한 노드는 다음부터 root노드를 한번에 찾게 해줌
"""

def make_graph():
  graph = {
    "vertices": ['A', 'B', 'C', 'D', 'E', 'F', 'G'],
    "edges": [
      (7, 'A', 'B'),
      (5, 'A', 'D'),
      (7, 'B', 'A'),
      (9, 'B', 'D'),
      (8, 'B', 'C'),
      (7, 'B', 'E'),
      (8, 'C', 'B'),
      (5, 'C', 'E'),
      (5, 'D', 'A'),
      (9, 'D', 'B'),
      (7, 'D', 'E'),
      (6, 'D', 'F'),
      (5, 'E', 'C'),
      (7, 'E', 'D'),
      (8, 'E', 'F'),
      (9, 'E', 'G'),
      (7, 'E', 'B'),
      (6, 'F', 'D'),
      (8, 'F', 'E'),
      (11, 'F', 'G'),
      (11, 'G', 'F'),
      (9, 'G', 'E')
      ]
    }
  return graph


parent = dict()
rank = dict()

def make_set(node):
  parent[node] = node
  rank[node] = 0

def find(node):
  if parent[node] == node:
    return node
  root = find(parent[node])
  # path-compression기법을 사용하여 한번 find하면 parent를 root로 바꿔버림
  parent[node] = root
  return root


def union(u,v):
  # root의 랭크를 비교하고 짧은쪽이 긴쪽에 붙어야함
  # rank를 ++ 해주는 경우도 추가해야함
  root_u = find(u)
  root_v = find(v)
  
  # union-by-rank 기법
  if rank[root_u] > rank[root_v]:
    parent[root_v] = root_u
    rank[root_u] += 1
  else:
    parent[root_u] = root_v
    rank[root_v] += 1

def kruskal(graph):
  mst = list()

  # 부분집합 확인을 위한 set 만들기
  for node in graph["vertices"]:
    make_set(node)

  # 노드들 연결시켜주기
  edges = sorted(graph["edges"])

  for edge in edges:
    weight, vertex_u, vertex_v = edge

    if find(vertex_u) != find(vertex_v):
      mst.append(edge)
      union(vertex_u,vertex_v)

  return mst


if __name__ == '__main__':
  graph = make_graph()
  answer = kruskal(graph)
  print(answer)

 

# 시간복잡도

1. set을 만들기 위해 Vertex(노드)의 개수만큼 반복문이 돌아감. O(v)

2. weight를 가장 낮은 기준으로 정렬(퀵소트) 하여 하나씩 뽑음. 퀵소트의 시간복잡도 O(n*log n) == O(e * log e), e == edge

3. union - find를 사용할때의 시간복잡도를 계산, 두 기법을 사용하여 최적화 시켰기 때문에 O(e) 

즉, 1,3은 상쇄되고 가장 긴 O(e*log e ) 의 시간복잡도를 가짐