크루스칼 알고리즘 - 파이썬

1. 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘입니다.

2. 그리디 알고리즘으로도 분류됩니다.

3. 구체적인 동작 과정은 아래와 같습니다.

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

   3.2 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인합니다.

      3.2.1 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킵니다.

      3.2.2 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않습니다.

4. 모든 간선에 대하여 3.2번의 과정을 반복합니다.

---

[초기 단계] 아래와 같은 노드 간 간선 정보가 있다고 했을 때, 그래프의 모든 간선 정보에 대하여 우선 오름차순 정렬을 수행합니다. 

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

실제 비용에 대해서 오름차순을 수행하면 아래와 같으며, 비용이 적은 간선부터 처리를 하게 됩니다.

비용

7

13

23

25

29

34

35

53

75

---

[Step 1] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (3,4)를 선택하여 Union 처리를 수행합니다.

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

---

[Step 2] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (4,7)를 선택하여 Union 처리를 수행합니다.

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

---

[Step 3] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (4,7)를 선택하여 Union 처리를 수행합니다.

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

---

[Step 4] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (6,7)를 선택하여 Union 처리를 수행합니다.

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

그런데 여기서 25의 비용인 (6,7) 간선을 처리하려고 해보니 노드 6과 노드 7은 같은 부모 노드(3)갖고 있으므로, 여기서 사이클이 발생한다고 판단하여 간선을 연결처리 하지 않습니다.

---

[Step 5] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (1,2)를 선택하여 Union 처리를 수행합니다.

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

---

[Step 7] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (2,3)를 선택하여 Union 처리를 수행합니다.

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

여기서 간선 (2,3)은 2번 노드의 부모 노드와 3번 노드의 부모 노드가 같으므로 처리하지 않도록 합니다.

 

---

[Step 8] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (5,6)를 선택하여 Union 처리를 수행합니다.

간선	(1,2)	(1,5)	(2,3)	(2,6)	(3,4)	(4,6)	(4,7)	(5,6)	(6,7)
비용	29	75	35	34	7	23	13	53	25
순서	Step 5	Step 9	Step 7	Step 6	Step 1	Step 3	Step 2	Step 8	Step 4

여기서 간선 (1,5)은 1번 노드의 부모 노드와 5번 노드의 부모 노드가 같으므로 처리하지 않도록 합니다.

---

# 특성 원소가 속한 집합을 찾기
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

# 노드의 개수와 간선 (Union 연산)의 개수 입력 받기
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(cost, a, b, parent)
print(result)

# 입력
# 7 9
# 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