신장 트리 - 크루스칼 알고리즘

신장 트리(Spanning Tree)는 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다.

가능한 신장 트리 예시

 

이 글은 신장 트리의 정의와 특성, 그리고 그것의 응용 분야와 관련 알고리즘에 대해 설명합니다.

 

신장 트리의 정의와 특징

 

1. 모든 노드 포함

 

신장 트리는 원본 그래프의 모든 노드를 포함하는 부분 그래프입니다. 이는 어떤 노드도 제외되지 않는다는 것을 의미합니다.

 

 

2. 사이클이 없는 구조

 

신장 트리는 사이클을 포함하지 않습니다.

이것은 트리 구조이기 때문에, 어떠한 경로를 따라가도 동일한 노드를 두 번 방문하지 않는다는 것을 의미합니다.

 

3. 신장 트리 알고리즘

 

1) 크루스칼(Kruskal) 알고리즘

이 알고리즘은 간선을 가중치 순으로 정렬한 후, 사이클을 형성하지 않는 방식으로 간선을 선택하여 신장 트리를 구성합니다.

 

2) 프림(Prim) 알고리즘

프림 알고리즘은 시작 노드에서 출발하여 점진적으로 최소 가중치 간선을 선택하여 신장 트리를 확장합니다.

 

 

크루스칼 알고리즘

이 알고리즘의 주요 목적은 가중치가 부여된 연결 그래프에서 간선의 가중치 합이 최소가 되도록 하는 신장 트리를 찾는 것입니다.

 

우리는 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장 트리로 찾아야 할 때가 있습니다.

 

크루스칼 알고리즘의 사용 예시를 들어 설명하겠습니다. 

 

 

가정해 봅시다. 

 

가상의 도시가 5개 있고, 이 도시들을 연결하는 도로가 있습니다.

도로마다 거리(가중치)가 있으며, 최소한의 도로를 사용하여 모든 도시를 연결하는 최소 신장 트리(MST)를 찾는 것이 목표입니다.

다음은 도시와 도로의 정보를 표로 나타낸 것입니다.

   A--2--B
   |     |
   1     3
   |     |
   C--4--D
    \   /
     \ /
      E

 

크루스칼 알고리즘의 동작 단계는 다음과 같습니다.

1. 모든 도로를 거리(가중치)에 따라 오름차순으로 정렬합니다.

2. 가장 짧은 거리의 도로부터 시작하여, 해당 도로가 MST에 포함되어도 사이클을 생성하지 않는 경우, 그 도로를 MST에 추가합니다.

3. 단계 2를 모든 도로를 고려할 때까지 반복합니다. 이때, MST의 크기는 (도시의 수  - 1)이 될 때까지 도로를 추가합니다.

 

1단계

 

도로들을 가중치를 기준으로 이름차순으로 정렬한 결과는 다음과 같습니다.

(A - C, 1)

(A - B, 2)

(B - D, 3)

(C - D, 4)

(C - E, 4)

 

이것은 가중치가 낮은 순서대로 도로들을 정렬한 목록입니다.

이 목록을 사용하여 크루스칼 알고리즘을 적용하면 최소 신장 트리를 구할 수 있습니다.

 

 

2단계

 

1. (A - C, 1)을 MST에 추가하고, MST에는 (A-C, 1)만 포함됩니다.

MST: (A-C, 1)


   A
   |
   C

 

 

 

2. (A-B, 2)를 MST에 추가하고, MST에는 (A-C, 1)과 (A-B, 2)가 포함됩니다.

MST: (A-C, 1), (A-B, 2)


   A
  / \
 C   B

 

 

 

3. (B-D, 3)를 MST에 추가하고, MST에는 (A-C, 1), (A-B, 2), (B-D, 3)이 포함됩니다.

MST: (A-C, 1), (A-B, 2), (B-D, 3)

   A
  / \
 C   B
    /
   D

 

 

 

4. (C-D, 4)를 MST에 추가합니다. 이때 주의할 점은 (C-D, 4)를 추가하면 사이클이 생성되므로 이 도로는 무시됩니다.

 

 

 

5. (C-E, 4)를 MST에 추가하고 MST에는 (A-C, 1), (A-B, 2), (B-D,3), (C-E, 4)가 포함됩니다.

MST: (A-C, 1), (A-B, 2), (B-D, 3), (C-E, 4)


   A
  / \
 C   B
    / \
   D   E

 

 

 

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

# 부모 노드를 찾는 함수
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)

 

입력

6 9  
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
3 5 11
4 5 3
4 6 8
5 6 8

 

결과

23

 

 

 

소스코드 쪼개기(실행 순서대로)

 

입력

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))

 

맨 처음에는 parent는 모두 0으로 세팅됩니다.

그리고 비용, 출발노드, 도착노드 순으로 edges 리스트에 적재됩니다.

 

위에 입력 데이터를 입력하면 edges 리스트는 다음과 같이 적재됩니다.

[(5, 1, 2), (4, 1, 3), (2, 2, 3), (7, 2, 4), (6, 3, 4), (11, 3, 5), (3, 4, 5), (8, 4, 6), (8, 5, 6)]

 

 

 

그 다음엔 1단계 비용을 기준으로 정렬(오름차순)이 진행됩니다.

edges.sort()

# 정렬됨
[(2, 2, 3), (3, 4, 5), (4, 1, 3), (5, 1, 2), (6, 3, 4), (7, 2, 4), (8, 4, 6), (8, 5, 6), (11, 3, 5)]

 

 

 

이제 edges에서 간선을 하나 씩 확인하면서 최소 신장 트리 만들기가 진행됩니다.

# 간선을 순회하면서 최소 신장 트리를 만들기
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)

edge에서 비용, 출발노드, 도착노드를 추출하여 

두 노드의 부모 노드가 다르면(사이클을 형성하지 않으면!!) 두 노드를 연결하고 가중치를 결과가 더하게 됩니다.

가중치는 result에서 누적 덧셈해줍니다.

 

 

 

첫 간선정보는 (2, 2, 3)

2 - 3 도로이며 가중치는 2라는 의미입니다.

 

find_parent로 2와 3의 각각의 부모를 찾아옵니다. 

def find_parent(parent, x):
    if parent[x] != x:
        # 루트 노드가 아니면, 루트 노드를 찾을 때까지 재귀적으로 호출
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

 

해당 함수는 find_parent함수를 재귀적으로 호출하기 때문에 부모의 부모의 부모 이런 식으로 상위 부모를 가져오는 함수입니다.

경로 압축을 하였기 때문에 모든 노드와 부모를 일렬로 나열해서 살펴볼 필요는 없습니다.

 

2의 부모는 현재 2 (초기값에 자기자신을 부모로 선정함)

3의 부모는 현재 3입니다.

 

 

 

 

그럼 if절 find_parent(parent, a) != find_parent(parent, b):

부모가 서로 다르기 때문에 union 융합이 진행됩니다.

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

부모 2와 3중  2가 작기때문에 2가 3의 부모가 되는 것입니다.

 

 

 

이 루틴이 최소 신장 트리를 만들때까지 이어집니다.