[컴퓨터알고리즘] 15. 최소신장트리

Minimum Spanning Tree

- 무방향 연결 가중치 그래프. n개의 모든 정점 n-1개의 간선으로 연결.

- MST는 유일하지 x

 

전체 트리의 가중치합..

 

GENERIC-MST -> A는 매 반복에서 선택된 안전간선들의 집합.

A에 대해 safe edge (u,v)를 찾아서 A에 합한다. 그것을 A 가 최소신장트리 되기 전까지 반복

GENERIC-MST(G,w)
  A<-∅
  while A does not form a spanning tree do
     find a safe edge(u,v) for A
     A <- A U {(u,v)}
  return A

 

크루스칼(Kruskal) 알고리즘

- forest를 이룸.

- 가중치값 최소 간선 선택함. (cycle 생기지 않게)

프림(Prim) 알고리즘

- single tree가 계속 확장됨. (시작정점o)

- 트리에 있지 않은 정점을 트리에 연결시키는 가중치값 최소 간선 선택함.

 

Kruskal 알고리즘의 실행

- 간선이 잇는 정점 이미 같은 집합 안에 있는 경우 (cycle 생기는 경우) 해당 간선은 버려야함!!

- Disjoint-Set Data Structure 서로소 집합구조

- Disjoint Set Union 을 통해 루트노드가 같은지 확인한다 (discard 할 수 있는 원리)

 

크루스칼 의사코드

- FIND-SET(u) != FIND-SET(v)는 u, v가 같은 트리에 속하지 않음을 확인한다

- 간선 (u,v)가 cycle 형성하거나 해서 추가될 수 없다면 버려진다.

- 그렇지 않으면 A에 추가되고 u, v를 union 한다

MST-KRUSKAL(G,w)
    A <- ∅
    for each vertex v∈V[G] do
    	MAKE-SET(V)
    SORT the edges of E by nondecreasing weight w
    for each edge(u,v)∈E in nondecreasing order do
    	if FIND-SET(u) != FIND-SET(v) then
            A <- A U {(u,v)}
            UNION(u,v)
    return A

 

Prim 알고리즘의 실행

- 우선순위 큐 Q에 모든 정점을 담고 시작한다. 트리에 속하지 않는 정점들은 Q에 남아있다.

- 트리에서 갈 수 있는 정점들 중 거리가 최소인 정점을 선택하는 것.

- key[v] = 현재 트리에서 갈 수 있는 최소 거리. (없으면 무한대)

 

MST-PRIM 의사코드

  Q <- V[G] 넣고 시작한다.

MST-PRIM(G,w,r)
    Q <- V[G]
    for each u ∈ Q do
        key[u] <- 무한대
    key[r] <- 0
    π[r] <- NIL
    BUILD-MIN-HEAP(Q) # Q로 최소힙만들기
    while Q != ∅ do
    	u <- EXTRACT-MIN(Q) # 가장 가까운 정점 추출
        for each v ∈ Adj[u] do # 인접리스트 원소들 거리 갱신
            if v ∈ Q and w(u,v) < key[v] then
                π[v] <- u # v의 부모 u 찾아줌
                DECREASE-KEY(Q, v, w,(u,v)) # key[v] <- w(u,v) 절차 진행

ExtractMin, ChangeKey(DecreaseKey) 과정을 반복.