목록Kruskal (1)

justgo_developer

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

Kruskal의 알고리즘 - 에지들을 가중치의 오름차순으로 정렬한다.- 에지들을 그 순서대로 하나씩 선택해간다. 단, 이미 선택된 에지들과 사이클을 형성하면 선택하지 않는다.- n-1개의 에지가 선택되면 종료한다.노드가 9개이므로 에지가 8개까지만 하면 된다. 더하면 어짜피 사이클이 생김. ◆ 사이클 검사- 초기 상태 : 선택된 에지 없음- 각각의 연결요소를 하나의 집합으로 표현{a} {b} {c} {d} {e} {f} {g} {h} {i} MST-KRUSKAL(G, w)A
IT/알고리즘 2018. 1. 4. 15:27
이전 Prev 1 Next 다음