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

크루스칼 알고리즘이란?

최소 신장 트리(Minimum Spanning Tree)를 구하는 알고리즘 중 하나로 최소 신장 트리는 가중치 그래프에서 모든 정점을 연결하면서 그 가중치의 합이 최소가 되는 트리를 의미한다.

 

크루스칼 알고리즘은 간선의 개수에 따른 시간 복잡도가 O(E log E)이다. 여기서 E는 간선의 개수를 의미한다. 따라서 크루스칼 알고리즘은 간선의 수가 적을 때 효율적으로 동작한다.

크루스칼 알고리즘은 네트워크 연결, 도로 건설 등 다양한 응용 분야에서 최적의 해를 구하는데 사용된다.

 

 

예시)

# 부모 노드를 찾는 함수
def find(parent, v):
    if parent[v] != v:
        parent[v] = find(parent, parent[v])
    return parent[v]

# 두 부모 노드를 합치는 함수
def union(parent, rank, v1, v2):
    root1 = find(parent, v1)
    root2 = find(parent, v2)

    if rank[root1] < rank[root2]:
        parent[root1] = root2
    elif rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root2] = root1
        rank[root1] += 1

# 크루스칼 알고리즘 함수
def kruskal(graph):
    minimum_spanning_tree = []  # 최소 신장 트리를 저장할 리스트
    edges = []  # 간선 리스트

    # 그래프의 간선을 간선 리스트에 저장
    for v in graph:
        for neighbor in graph[v]:
            edges.append((v, neighbor, graph[v][neighbor]))

    # 간선을 가중치를 기준으로 오름차순 정렬
    edges.sort(key=lambda x: x[2])

    parent = {}  # 부모 노드를 저장하는 딕셔너리
    rank = {}  # 랭크를 저장하는 딕셔너리

    for v in graph:
        parent[v] = v
        rank[v] = 0

    for edge in edges:
        v1, v2, weight = edge

        if find(parent, v1) != find(parent, v2):
            union(parent, rank, v1, v2)
            minimum_spanning_tree.append(edge)

    return minimum_spanning_tree


# 그래프 예시
graph = {
    'A': {'B': 7, 'D': 5},
    'B': {'A': 7, 'D': 9, 'C': 8, 'E': 7},
    'C': {'B': 8, 'E': 5},
    'D': {'A': 5, 'B': 9, 'E': 15, 'F': 6},
    'E': {'B': 7, 'C': 5, 'D': 15, 'F': 8, 'G': 9},
    'F': {'D': 6, 'E': 8, 'G': 11},
    'G': {'E': 9, 'F': 11}
}

# 크루스칼 알고리즘 실행
minimum_spanning_tree = kruskal(graph)

# 결과 출력
print("Minimum Spanning Tree:")
for edge in minimum_spanning_tree:
    print(edge)

 

# find() 함수
재귀적으로 부모 노드를 찾는 함수로 parent는 부모 노드를 저장하는 딕셔너리이며, v는 해당 노드이다. 함수는 현재 노드 v의 부모 노드를 찾을 때까지 재귀적으로 호출하고, 부모 노드를 찾았을 경우 부모 노드를 해당 노드에 업데이트 한다.. 마지막으로 최종 부모 노드를 반환합니다.

 

# union() 함수

두 개의 집합을 합치는 함수로 parent는 부모 노드를 저장하는 딕셔너리이고, rank는 각 노드의 랭크를 저장하는 딕셔너리이다. v1과 v2는 합칠 두 개의 노드이며 함수는 각 노드의 최상위 부모 노드를 find() 함수를 통해 찾고, 두 개의 부모 노드를 비교하여 더 낮은 랭크를 가진 부모 노드일 경우 작은 노드의 부모노드에 해당 부모노드를 대입한다.. 랭크가 같은 경우에는 한 쪽을 부모로 설정하고 해당 부모의 랭크를 증가시킨다.

 

# kruskal() 함수

크루스칼 알고리즘을 수행하는 함수로 graph는 주어진 그래프를 나타내는 딕셔너리이다. 함수는 빈 리스트인 minimum_spanning_tree와 edges 리스트를 초기화한다.

다음으로, graph의 각 노드와 이웃한 노드들을 순회하며 edges 리스트에 간선 정보를 추가하고 각 간선은 출발 노드(v1), 도착 노드(v2), 가중치(weight)로 구성된다.

간선 리스트 edges를 가중치를 기준으로 오름차순으로 정렬한다.

parent와 rank 딕셔너리를 초기화하고, 각 노드를 자기 자신의 부모로 설정하여 랭크를 0으로 초기화한다.

정렬된 간선 리스트 edges를 순회하면서 find() 함수를 사용하여 출발 노드와 도착 노드의 최상위 부모를 확인하고, 부모가 다를 경우 union() 함수를 사용하여 두 노드를 합친다. 이때, 합치기 전에 사이클 여부를 확인하기 위해 find() 함수를 통해 부모 노드가 같은지 확인하며 최종적으로 최소 신장 트리인 minimum_spanning_tree 리스트를 반환한다.