[알고리즘] 크루스칼 알고리즘

Hyo Kyun Lee·2022년 1월 13일

알고리즘 크루스칼 알고리즘

알고리즘

목록 보기

12/45

12. 크루스칼(Kruskal) 알고리즘

가장 적은 비용(간선연결)을 통해 모든 노드를 연결하는 방법을 도출하는 알고리즘이다.

최적의 비용을 도출하는 알고리즘을 공부하는 것부터 시작한다.

12-1. 알고리즘 구현 시 고려사항

크루스칼 알고리즘을 구현할 때 만족해야하는 조건이 4가지 존재한다.

모든 노드들은 연결되어있는 상태(하나의 graph로 구성)이다.
최소한의 비용(간선)이다(최소비용 신장트리).
간선개수가 모든 노드의 개수 -1을 만족한다.
사이클(자식노드가 2개이하, 노드로 가는 경로가 반드시 1개만 존재)이 없다.

12-2. 구현과정

크루스칼 알고리즘은 union-find(노드를 합치고, 부모노드를 일치시키는 알고리즘)을 활용한다.

먼저 모든 노드들에 대해 간선정보(노드 간 비용)를 오름차순 정렬한다.
사이클테이블을 확인하면서, 사이클테이블에서 연결되어있지않은 경우(부모노드가 다른 경우)에 한해서만 비용을 누적(그래프 추가)한다.
사이클테이블은 앞서 union-find 알고리즘에서 구현한 node array와 동일하다.

12-3. 알고리즘

array = [0, 1, 2, 3, 4, 5, 6, 7, 8]


# 부모노드 찾기(1차구성)
def getParent(array, value):
    if array[value] == value:
        return array[value]
    return getParent(array, array[value])


# 부모노드 합치기(2차구성)
def unionParent(array, value1, value2):
    value1 = getParent(array, value1)
    value2 = getParent(array, value2)
    if value1 < value2:
        array[value2] = value1
    else:
        array[value1] = value2


# 같은 부모를 가지는지(같은 graph의 node인지) 확인하기
def findParent(array, value1, value2):
    value1 = getParent(array, value1)
    value2 = getParent(array, value2)
    if value1 == value2:
        return True
    else:
        return False

#간선정보
edges = [
    [12, 1, 7],
    [28, 1, 4],
    [67, 1, 2],
    [24, 2, 4],
    [62, 2, 5],
    [20, 3, 5],
    [37, 3, 6],
    [13, 4, 7],
    [45, 5, 6],
    [73, 5, 7]
]

edges.sort()
result = 0

for edge in edges:
    cost, node1, node2 = edge
    if findParent(array, node1, node2):
        pass
    else:
        unionParent(array, node1, node2)
        result = result + cost

print(result)