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

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

• 신장 트리: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
• 최소 신장 트리 알고리즘: 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘
  • 대표적인 최소 신장 트리 알고리즘: 크루스칼 알고리즘

---

• 알고리즘 동작 과정
  1. 간선 데이터를 비용에 따라 오름차순으로 정렬
  2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
     1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
     2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음
  3. 모든 간선에 대해 2번의 과정을 반복

---

• 크루스칼 알고리즘 소스코드

  • 입력 예시

    # 노드 7개, 간선 9개
    7 9
    # 1번 노드에서 2번 노드로 가는 비용: 29
    1 2 29
    1 5 75
    2 3 35
    2 6 34
    3 4 7
    4 6 23
    4 7 13
    5 6 53
    6 7 25

  • 소스코드

    def find_parent(parent, x):
        if parent[x] != x:
            parent[x] = find_parent(parent, parent[x])
        return parent[x]
    
    def union_parent(parent, a, b):
        a = find_parent(parent, a)
        b = find_parent(parent, b)
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
    
    v, e = map(int, input().split())
    parent = [0] * (v+1)
    
    # 모든 간선을 담을 리스트와 최종 비용을 담을 변수
    edges = []
    result = 0
    
    for i in range(1, v+1):
        parent[i] = i
    
    for _ in range(e):
        a, b, cost = map(int, input().split())
        edges.append((cost, a, b))
    
    # 간선을 비용순으로 정렬
    edges.sort()
    
    for edge in edges:
        cost, a, b = edge
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            result += cost
    
    print(result)

  • 출력

    159