최소비용신장트리(minimum spanning tree)-2

Kruskal의 알고리즘

- 에지들을 가중치의 오름차순으로 정렬한다.

- 에지들을 그 순서대로 하나씩 선택해간다. 단, 이미 선택된 에지들과 사이클을 형성하면 선택하지 않는다.

- n-1개의 에지가 선택되면 종료한다.

노드가 9개이므로 에지가 8개까지만 하면 된다.

더하면 어짜피 사이클이 생김.

◆ 사이클 검사

- 초기 상태 : 선택된 에지 없음

- 각각의 연결요소를 하나의 집합으로 표현

{a} {b} {c} {d} {e} {f} {g} {h} {i}

MST-KRUSKAL(G, w)

A<-

for each vertex v ∈ V[G]

do MAKE-SET(v)   //각각의 노드들을 유일한 원소로 가지는 집합들을 만드렁라.

sort the edges of E into nondecreasing order by weight w

for each edge(u,v) ∈ E, taken in nondecreasing order by weight

do if FIND-SET(u) ≠ FIND-SET(v) //노드 v가 속한 집합을 찾아라

then A<- A∪{(u,v)}

UNION(u,v) //u와v가 속한 두집합을 하나로 합친다.

return A