본문 바로가기

MST2

15-2강. 최소비용신장트리 (Minimum Spanning Tree) (2) 최소비용신장트리 (Minimum Spanning Tree) Kruskal의 알고리즘 - 에지들을 가중치의 오름차순으로 정렬한다. - 에지들을 그 순서대로 하나씩 선택해 간다. 단, 이미 선택된 에지들과 사이클(cycle)을 형성하면 선택하지 않는다. - n-1개의 에지가 선택되면 종료한다. 위의 그래프에서, 모른 에지들을 작은 것부터 큰 것 순으로 정렬해 두었다고 가정하자. (a) : 가장 가중치(weight)가 작은 에지(1)를 선택한다. => 내가 선택한 에지들은 cycle을 형성하지 않는다. (왜? 에지가 하나밖에 선택되지 않았으니까) (b) : 그 다음으로 가중치(weight)가 작은 에지(2)를 선택한다. => cycle을 형성하지 않는다. (c) : 그 다음으로 가중치(weight)가 작은 에.. 2020. 12. 13.

15-1강. 최소비용신장트리(Minimum spanning tree) 최소비용신장트리 (Minimum Spanning Tree) - 입력 : n 개의 도시, 도시와 도시를 연결하는 도로 비용 - 문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다. 해가 유일하지는 않다.. 예) (b, c) 대신에 (a, h)가 되어도 된다. -> 비용이 같고, 다 연결되기 때문이다. * 최소비용신장트리의 답은 항상 트리가 된다. 왜? (트리 : 싸이클이 없는 연결된(connected) 무방향 그래프) : cycle이 있다는 말은 이쪽 방향으로 가도 저쪽 방향으로 가도 되는데, 이 경우 한 쪽의 길이 끊어져도 반대 방향으로 갈 수 있게 된다. 따라서 우리는 최소비용을 원하므로 cycle이 있는 그래프는 이 경우에서 제외한다. - 어떤 MST(Minimun Spanning Tree)의.. 2020. 12. 11.

이전 1 다음

티스토리툴바