[알고리즘, 파이썬] 크루스칼 알고리즘 - 3

이번 포스트에서는 파이썬으로 크루스칼 알고리즘을 구현해 보도록 하겠습니다. 

(게시글의 자료들은 잔재미코딩(https://www.fun-coding.org/Chapter20-prim-live.html) 사이트를 참조하였습니다)

파이썬과 컴퓨터 사이언스(고급 알고리즘): 최소 신장 트리 (Prim's algorithm) - 잔재미코딩

먼저 앞선 포스트에서 다룬 그래프를 다음과 같은 그래프를 딕셔너리 형태로 구현하도록 하겠습니다. 

mygraph = { 'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'edges': [ (7, 'A', 'B'), (5, 'A', 'D'), (7, 'B', 'A'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'), (8, 'C', 'B'), (5, 'C', 'E'), (5, 'D', 'A'), (9, 'D', 'B'), (7, 'D', 'E'), (6, 'D', 'F'), (7, 'E', 'B'), (5, 'E', 'C'), (7, 'E', 'D'), (8, 'E', 'F'), (9, 'E', 'G'), (6, 'F', 'D'), (8, 'F', 'E'), (11, 'F', 'G'), (9, 'G', 'E'), (11, 'G', 'F') ] } parent = dict() # 각노드의 부모노드를 저장하기 위한 딕셔너리 선언 rank = dict() # 마찬가지로 각 집합의 rank를 저장하기 위한 dict 선언 ''' def find(node) : 만약 자신이 루트 노드가 아니라면, 재귀적으로 조회하여 루트노드를 찾고 그것을 그 노드의 parent 노드로 딕셔너리에 저장합니다. ''' def find(node): # path compression 기법을 사용하여 각 노드의 루트노드를 다이렉트로 참조한다 if parent[node] != node #자신이 루트 노드가 아닐 때, 위에 부모노드가 존재할 때 parent[node] = find(parent[node]) return parent[node] def union(node_v, node_u): #앞서 정의한 union 규칙에 따라 코드를 작성합니다. root1 = find(node_v) root2 = find(node_u) #만약 root1 그룹의 rank가 root2그룹 rank값보다 크다면, roo2의 부모노드를 root1으로 지정(합침) if rank[root1] > rank[root2] : parent[root2] = root1 #root1 rank가 root2보다 작거나 같다면 else: parent[root1] = root2 if rank[root1] = rank[root2]: #만약 같다면 root2그룹 랭크를 1증가시키고 두 그룹을 합침 rank[root2] +=1 #초기화 함수 def makeset(node): parent[node] = node #초기에 자기 자신이 루트노드 rank[node] = 0 def kreuskal(graph): mst = list() #mst를 리스트 형태로 저장 #초기화 for node in graph['vertices']: makeset(node) #간선을 weight가 작은 순서대로 sorting, 파이썬 내장 sort함수를 사용 edges = graph['edges'] edges.sort() #weight가 작은 순서대로 sorting 하였으므로 차례대로 조회하며 union_find를 실행한다 for edge in edges: weight, node_v, node_u = edge if find(node_v) != find(node_u): #만약 두 노드가 같은 집합이 ㅏ니라면 union(node_v, node_v) mst.append(edge) #추가된 간선을 edge에 추가 return mst

 

 

 

크루스칼 연산 결과 값 

 

이제 구현까지 살펴 보았으니 시간복잡도를 살펴봅시다. 

 

시간 복잡도

• 크루스컬 알고리즘의 시간 복잡도는 O(E log E)
  • 다음 단계에서 2번, 간선을 비용 기준으로 정렬하는 시간에 좌우됨
    (즉 간선을 비용 기준으로 정렬하는 시간이 가장 많이 든다)
  • 모든 정점을 독립적인 집합으로 만든다. - 복잡도 O(V) 
  • 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
    • 퀵소트를 사용한다면 시간 복잡도는 O(n log n) 이며, 간선이 n 이므로 O(E log E)
  • 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)
    • union-by-rank 와 path compression 기법 사용시 시간 복잡도가 결국 상수값에 가까움, O(1)

 

이상으로 크루스칼 알고리즘에 대한 포스트를 마치도록하겠습니다.