최소비용신장트리 -2

kruskal 알고리즘

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

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

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

- 가중치가 작은 순서대로 연결하면서 순환이 되면 연결하지 않는다.

 

순환여부 확인

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

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

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

-> {a}, {b}, {c}, {d}, {e}, {f}, {g, h}, {i}

-> {a}, {b}, {c, i}, {d}, {e}, {f}, {g, h}

-> {a}, {b}, {c, i}, {d}, {e}, {f, g, h}

-> {a, b}, {c, i}, {d}, {e}, {f, g, h}

-> {a, b}, {c, f, g, h, i}, {d}, {e}

-> {a, b}, {c, f, g, h, i, d}, {e}

-> {a, b, c, f, g, h, i, d}, {e}

-> {a, b, c, f, g, h, i, d, e}

 

수도코드