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

1. 크루스칼 알고리즘 동작 원리...?

a) 간선의 가중치를 오름차순으로 sort

b) (sort 되었으니까) 간선을 하나씩 확인하며 

    사이클 발생 O: MST에 포함 X

    사이클 발생 X: MST에 포함 O

c) 모든 간선에 대해 b) 과정을 해줌

 

사실 수업을 들을 때도 말로만 설명을 들으니까 확실히 이해가 되지 않아서

코드를 짠 후, 그 코드를 분석해보았다.

 

2. 크루스칼 알고리즘 코드 분석

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() #각각의 노드마다 부모노드 저장
rank = dict() #각각의 노드마다 rank

def make_set(node): #초기화 함수)
    parent[node] = node
    rank[node] = 0

def find(node): #path compression기법 사용하여 최상위 정점 확인
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]
    
def union(node_v, node_u):
    #각각의 루트노드를 찾아내기(find함수 활용)
    root1 = find(node_v)
    root2 = find(node_u)
    
    #union-by rank 기법
    if rank[root1]>rank[root2]: #rank가 낮은 root노드의 parent를 rank가 높은 곳과 연결
        parent[root2] = root1
    else:
        parent[root1] = root2
        
        if rank[root1] == rank[root2]: #같으면 일단 합쳐주고 붙임 당한 노드의 랭크를 올려주기
            rank[root2] += 1
                  
def kruskal(graph):
    mst = list()
    
    #노드 초기화
    for node in graph['vertices']:
        make_set(node)
     
    #graph의 edge를 간선 가중치 기준으로 오름차순 sort
    edges = graph['edges']
    edges.sort()#edges는 sort된 간선정보
    
    for edge in edges: #sort된 간선들을 하나씩 합치는 작업(사이클 없이)
        weight, node_v, node_u = edge
        if find(node_v) != find(node_u):
            union(node_v, node_u)
            mst.append(edge)
        
    return mst

• 초기 세팅: edge 정보를 (weight, node_v, node_u) 형태로 세팅 / 각 노드마다 부모 노드를 저장하는 parent(dictionary) / 각 노드마다의 rank를 저장하는 rank(dictionary)

1. 모든 정점 A~G에 대해 make_set() 함수를 통해 초기화를 해줌 (parent를 자기 자신으로 설정, rank를 0으로 설정)
2. graph dictionary에 있는 edges 리스트를 weight 기준으로 sort 하여 edges 리스트에 담아줌
3. edges안에 있는 요소들을 하나씩 훑어주면서 

      a) node_v와 node_u가 같은 root_node를 가지고 있으면 skip -> 사이클이 생길 수 있기 때문

     

      예를 들어 이 상황에서 C와 F를 연결한다고 하자

      C와 F의  root_node는 모두 E이고 둘을 연결했을 때 사이클이 생기는 것을 확인할 수 있다.

 

      b) 사이클 생성 여부를 판단한 뒤

     

      c) path compression기법을 사용하여 node_v와 node_u의 root_node를 찾아낸다.

 

      d) union-by rank기법을 사용하여 rank를 적절히 조절해준 뒤, 노드를 연결시켜준다.

 

      e) b)에서 사이클을 만들지 않은 edge들을 weight 오름차순대로 하나씩 mst리스트에 append 해주면

         mst에 들어간 edge들을 순서대로 확인할 수 있다.

 

정리를 나름대로 해보긴 했는데, 쉽게 설명을 못한 것 같네요 ㅠㅠ 

return된 mst 리스트

 

3. 시간 복잡도...?

• O(E log E)  E는 간선

1. 각 노드를 초기화할 때 -> O(V)

2. 간선을 가중치 기준으로 오름차순 sort 할 때 -> O(E log E)  퀵 소트 사용하면

3. 간선을 한 바퀴 돌면서 합치는 과정 -> O(E)

 

결국 sorting 하는 프로세스를 제외하면 상수 시간 복잡도이기 때문에

전체 시간 복잡도는 O(E log E)이다.