최소 스패닝 트리_크루스칼,프림 알고리즘

최소 스패닝 트리?

스패닝 트리 
n개의 정점(노드)를 가지는 그래프의 최소 간선의 수는 n-1개이고 n-1개의 간선으로 연결되어 있으면 트리형태과 되며 이것은 스패닝 트리가 된다.
즉 그래프의 일부 간선을 선택해서 만든트리

MST(최소 스패닝 트리)
스패닝 트리중에서 사용된 간선들에 가중치가 있을경우 이 간선의 합이 최소인 트리이다.
최소 스패닝 트리는 단순히 가장 가중치가 적은 간선들을 사용한다고 해서 얻어지는것이 아니다.

MST특징은 아래와 같다.

1.  간선의 가중치 합이 최소여야한다.
2. n개의 정점을 가지는 그래프에 대하여 반드시(n-1)개의 간선만을 사용한다.
3. 사이클이 포함되어서는 안된다.

---

MST를 구현 알고리즘

1. 크루스칼(KrusKal)알고리즘
2. 프림(Prim)알고리즘

 

 

MST예시 크루스칼과 프림을통해 구할 수 있다.

1. 크루스칼 알고리즘

MST(Minimum Spanning Treee) 가 최소가중치(비용)으로 구성되며 사이클을 포함하지 않음의 조건에 근거, 

greedy method를 기초로한다.

greedy method란 당장 눈앞에 보이는 최적의 상황만 고르는 방법을 의미한다.

 

각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다. 사이클을 이루는경우 다음 최소비용간선을 선택 모든 노드가 이어질때까지 반복한다.

크루스칼 알고리즘을 구현시 Union-Find  연산을 활용한다.

 

크루스칼알고리즘 활용 백준 1197

# 특정 원소가 속한 집합을 찾기
import sys
input = sys.stdin.readline

def find(parent, x):
    if parent[x] == x:
        return x
    parent[x] = find(parent, parent[x])
    return parent[x]


# 두 원소가 속한 집합을 합치기 (간선 연결한다고 생각!)
def union(parent, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)

    if rootA < rootB:
        parent[rootB] = rootA 
    else:
        parent[rootA] = rootB


# 입력받기
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, a) != find(parent, b):
        union(parent, a, b)
        result += cost

print(result)

---

2. 프림 알고리즘

시작 정점에서부터 출발해 신장트리의 집합을 단계적으로 확장해나가는 방법이다. 크루스칼과 마찬가지로 greedy method를 기초로한다.

 

1. 임의의 정점을 선택, '연결된 노드 집합'에 삽입
2. 선택된 정점에 연결된 간선들을 간선 리스트에 삽입
3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서,
   1. 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵함(cycle 발생을 막기 위함)
   2. 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리'에 삽입
4. 추출한 간선은 간선 리스트에서 제거
5. 간선 리스트에 더 이상의 간선이 없을 때까지 3-4번을 반복

참고 : https://devlog-wjdrbs96.tistory.com/101

Prim 알고리즘 이란?