[알고리즘] 크루스칼 알고리즘 ( feat. union - find 알고리즘 )

[신장 트리]

• 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 신장 트리라고 한다.
• 아래는 원래의 그래프(위)에 대한 부분 그래프(아래), 신장 트리의 예 이다.

원래의 그래프

부분 그래프 (신장 트리)

---

[크루스칼 알고리즘]

• 그래프의 간선에 비용이 적혀있다고 하자.
• 신장 트리의 모든 간선에 대하여, 비용이 합이 가장 적겠끔 하는 신장 트리를 구하는 알고리즘을 최소 신장 트리 알고리즘이라고 한다. 
• 대표적인 최소 신장 트리 알고리즘으로 크루스칼 알고리즘이 있다.
• 그리디 알고리즘으로 분류된다.

간선 데이터를 비용에 따라 오름차순으로 정렬한다.

간선	3, 4	4, 7	4, 6	6, 7	1, 2	2, 6	2, 3	5, 6	1, 5
비용	7	13	23	25	29	34	35	53	75

 

간선을 하나 하나 체크해가며 그래프가 사이클을 이루고 있다면, 제외한다.

다음과 같이 길이 7, 13, 23 을 포함해 나가다가 길이 25에서 사이클을 이루자 제거하였다.

최종 간선은 아래와 같다.

 

 

 

def find_parent(X):
    if parent[X] != X:
        parent[X] = find_parent(parent[X])
    return parent[X]

def union(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b :
        parent[b] = a
    else: parent[a] = b

v, e = map( int, input().split())
parent = [i for i in range(v+1)]

# 모든 간선과 최종 비용
edges = []
result = 0

# 모든 간선에 대한 정보 입력
for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))        # 비용, a노드, b노드 순서로 작성

edges.sort()

for edge in edges:
    cost, a, b = edge

    # 사이클이 발생할 경우 패스
    if find_parent(a) == find_parent(b):
        continue

    # 사이클이 발생하지 않으면, 비용을 더함
    else:
        union(a, b)
        result += cost
   
 print(result)

 

마지막에 아래와 같이 코드를 정리하는게 보다 깔끔하겠지만, 가독성을 위해 일부로 위와 같이 적었다.

if find_parent(a) != find_parent(b) :
    union(a, b)
    result += cost

참고한 책 ; 나동빈 (2020). <이것이 취업을 위한 코딩 테스트다 with 파이썬>. 서울시: 한빛미디어.

 

 

 

 

 

p.s.

크루스칼 알고리즘에서 find_parent(X) 함수를

DP 로 작성할 경우 다음의 예외 사항이 생긴다.

dp 테이블에 저장할 경우,

4번 노드는 처음에 연결되어 부모노드가 2임에 반해,

2번 노드와 1번 노드가 연결 된 뒤, 연결된 3번 노드의 경우 부모노드는 1이다.

3번 노드와 4번 노드를 봤을 때 부모노드가 서로 다르므로 크루스칼 알고리즘은 사이클이라 판단하지 못한다.

 

반면에 위에서처럼 재귀로 구현할 경우,

3번 노드와 4번 노드 모두 바로 위의 부모노드인 2번 노드를 참고하게 되고,

2번 노드의 부모노드는 1번 노드이므로 두 노드의 부모 노드가 같다는 걸 알 수 있고,

따라서 사이클이라 판단하게 된다.

 

따라서 크루스칼 알고리즘을 구현 할 때

find_parent 함수는 재귀로 구현해야한다.