[파이썬 | 알고리즘] 크루스칼 알고리즘(Kruskal's algorithm)

print("크루스칼 구현")
kruskal(mygraph)

지난번에는 다익스트라 알고리즘(Dijkstra algorithm)에 대해 알아보았습니다.

이번에는 크루스칼 알고리즘(Kruskal's algorithm)에 대해 알아보겠습니다.

 

*해당 자료는 패스트캠퍼스 올인원 패키지 강의자료를 참고하였습니다.*

최소신장트리(Minimum Spanning Tree)의 조건

MST라고 불리는 최소신장트리의 조건

1.싸이클이 존재하지 않아야한다.(트리의 속성)

2.모든 노드가 서로 연결되어있어야한다.

3.간선의 가중치 합이 최소값이어야 한다.

 

조건 1,2번

최소신장트리 조건1,2

조건 3번

최소신장트리 조건3

대표적인 최소신장트리 알고리즘

🖍크루스칼 알고리즘(Kruskal's algorithm)

🖍프림 알고리즘(Prim's algorithm)

먼저 최소상신장트리 대표적인 알고리즘 중 크루스칼 알고리즘에 대해 알아보겠다.

크루스칼 알고리즘(Kruskal's algorithm) 접근

크루스칼 알고리즘을 해결하기 위해서는 Union-Find 알고리즘 기법이 활용된다.

즉 개별 집합을 하나의 집합으로 합치는 Union, 싸이클 존재여부를 판단하는 Find

알고리즘을 활용한다. 이때 시간복잡도 계산량이 O(N)이 될 수 있으므로 해당 문제를

해결하기 위해,  union-by-rank, path compression 기법을 사용함

Union

개별 집합

개별집합 -> 하나의 집합

 

Find

두 노드가 서로 같은 그래프에 속하는지(싸이클 존재) 두 정점의 최상위 정점 판단

Union & Find 알고리즘 기법

union-by-rank

union시 두 트리의 높이(rank)가 다르면 높이가 작은 트리를 높이가 큰 트리에 붙임

 

union시 두 트리의 높이(rank)가 같다면 한쪽의 트리 높이(rank)를 1 증가시키고, 다른 쪽 트리를 높인 트리에 붙임

path compression

Find를 실행한 노드에서 거쳐간 점들을 최상위 정점 바로 연결하는 기법

크루스칼 알고리즘(Kruskal's algorithm) 패턴 분석

1.모든 정점을 독립적인 집합으로 만든다.

2.모든 간선을 가중치 기준으로 정렬하고, 가중치가 작은 간선부터 양 끝의 두 정점을 비교한다.

3.두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한 후. rank를 조절한다.

rank 패턴

1.정점 V의 최상위 노드, U의 최상위 노드 rank가 서로 같디면 U의 자식노드를 V로 설정하고 U의 rank를 1증가시킨다.

2.정점 U의 최상위 노드가 V의 최상위 노드 rank보다 높다면  U의 자식노드를 V로 설정한다.

 

union-find패턴

*union기법: 점 V,U의 최상위 노드가 서로 다르다면 이는 다른 집합 -> 싸이클X -> 연결 O

  점 V,U의 최상위 노드가 서로 같다면 이는 같은 집합 -> 싸이클O -> 연결X*

*find기법: 점 V,U의 최상위 노드를 판단하기 위한 노드를 거치는 과정*

모든 정점은 독립적인 집합

graph = {
    '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')
    ]
}
edges = graph['edges']
edges.sort()
edges

모든 간선을 가중치 기준으로 정렬

가중치가 작은 간선부터 양 끝의 두 정점 비교

 

1.가중치 5 / 양 끝의 두 정점 A - D

 A의 최상위 정점 -> A / D의 최상위 정점 -> D  => 연결O

 A 최상위 rank = (A rank 0) / D최상위 rank = (D rank 0)

 A rank == D rank이므로 D의 자식을 A로 설정하고 D의 rank+1

 

 

2.가중치 5 / 양 끝의 두 정점 C - E

 C의 최상위 정점 -> C / E의 최상위 정점 -> E => 연결O

 C 최상위 rank = (C rank 0) / E최상위 rank = (E rank 0)

 C rank == E rank이므로 E의 자식을 C로 설정하고 E의 rank+1

 

 

3.가중치 6 / 양 끝의 두 정점 D - F

  D의 최상위 정점 -> D / F의 최상위 정점 -> F => 연결O

 D 최상위 rank = (D rank 1) / F최상위 rank = (F rank 0)

 D rank > F rank이므로 D의 자식을 A로 설정

 

 

4.가중치 7 / 양 끝의 두 정점 A - B

 A의 최상위 정점 -> D / B의 최상위 정점 -> B => 연결O

 A 최상위 rank = (D rank 1) / B최상위 rank = (B rank 0)

 D rank > B rank이므로 D의 자식을 B로 설정

 

 

5.가중치 7 / 양 끝의 두 정점 B - E

 B의 최상위 정점 -> D / E의 최상위 정점 -> E => 연결O

 B 최상위 rank = (D rank 1) / E최상위 rank = (E rank 1)

 D rank == E rank이므로 E의 자식을 D로 설정하고 E의 rank+1

 

 

6.가중치 7 / 양 끝의 두 정점 D - E

  D의 최상위 정점 -> E / E의 최상위 정점 -> E => 연결X

 

 

7. 가중치 8, 9 -> 6과 같이 각 점의 최상위 정점이 같음 => 연결X

 

8.가중치 9 / 양 끝의 두 정점 E - G

 E의 최상위 정점 -> E / G의 최상위 정점 -> G => 연결O

 E 최상위 rank = (E rank 2) / G최상위 rank = (G rank 0)

 E rank > G rank이므로 E의 자식을 G로 설정

9. 가중치 11 -> 6과 같이 각 점의 최상위 정점이 같음 => 연결X

 

더 이상의 간선이 존재하지 않으니 종료

크루스칼 알고리즘 구현 (파이썬 | Kruskal's algorithm)

graph = {
    '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()            #union-find 기법을 위한 부모노드
rank = dict()              #union-find 기법을 위한 rank


def find(node):              # find -> 사이클 존재여부 확인 -> 최상위 노드 확인
                             # path compression 기법  
    if parent[node] != node: # 현재 정점이 최상위 정점이 아니라면
        parent[node] = find(parent[node]) #재귀용법 (최상위 노드를 찾을 때 까지 call) 
    return parent[node]      # 현재 정점의 최상위 정점 리턴


def union(node_v, node_u):   # union -> 서로 다른 집합이면 연결
    root1 = find(node_v)     # root1은 정점 V의 최상위 정점 
    root2 = find(node_u)     # root2는 정점 U의 최상위 정점
    
    # union-by-rank 기법
    if rank[root1] > rank[root2]:        #root1(V)의 rank가 root2(U)의 rank보다 크다면
        parent[root2] = root1            #root1(V)의 자식이 root2(U)가 된다. 즉 U의 부모가 V가 된다.
        
    else:                                #root2(U)의 rank가 root1(V)의 rank보다 크다면
        
        parent[root1] = root2            #root2(U)의 자식이 root1(V)가 된다. 즉 V의 부모가 U가 된다.
        if rank[root1] == rank[root2]:   #root1(V)의 rank가 root2(U)의 rank와 같다면
            rank[root2] += 1             #root2(U)(부모)의 rank를 1증가한다.
    
    
def make_set(node):        
    parent[node] = node      #모든 정점을 부모정점으로 초기화
    rank[node] = 0           #모든 정점의 rank를 0으로 초기화

def kruskal(graph):
    mst = list()             #최소신장트리를 담을 리스트 선언
    
    # 1. 초기화
    for node in graph['vertices']: # 그래프 순회
        make_set(node)             # 그래프 데이터 초기화
    
    # 2. 간선 weight 기반 sorting
    edges = graph['edges']   #간선 초기화      
    edges.sort()             #모든 간선을 가중치 기준으로 정렬
    
    # 3. 간선 연결 (사이클 없는)
    for edge in edges:                   # 정렬 된 모든 간선 순회, 더 이상의 간선이 없을 때 까지
        weight, node_v, node_u = edge    # 간선의 가중치, 양 끝의 두 정점 V, U로 표현
        if find(node_v) != find(node_u): # 정점 V의 최상위 노드가 정점 U의 최상위 노드랑 다르다면
            union(node_v, node_u)        # 정점 V와 정점 U를 연결
            mst.append(edge)             # 연결한 정점 및 가중치 최소신장트리에 추가
    
    return mst                           # 최소신장트리 리턴

크루스칼 알고리즘 코드 테스트

 

 

테스트 결과

 

크루스칼 알고리즘 구현 코드가 정상적으로 구현됨

이상으로 [파이썬 | 알고리즘] 크루스칼 알고리즘 에 대해 알아보았습니다,