안녕하세요 저는 알고리즘을 처음 사용하고 최소 스패닝 트리를 이해하려고합니다.최소 스패닝 트리 알고리즘
저는 Cormen, Leiserson, Rivest 및 Stein의 "Introduction to Algorithms"책을 연구합니다. 나는 문장을 이해하는 데 어려움을 겪었습니다. ".. 컷 은을 의미하고, A의 가장자리가 컷을 교차하지 않으면 엣지의 집합 A를 의미합니다."
주어진 예에서 사진을 넣어 내 이해를 분명히하겠습니다. 우리는 또한 음영 에지 (d, e)는 이후의 절단 교차하지 않는 안 번째 모습에 도시 된 바와 같이 우리가 그래프를 절단 할 때 A minimum spanning tree for a connected graph.
1 way of viewing a cut (S,V-S) of the previous graph.
그래서 내 질문?
나를 설명하면 감사하겠습니다.
이것은 kruskal의 MST 알고리즘입니다. 하위 트리의 나머지 부분에서 모든 하위 트리를 잘라냅니다. 우리는 두 개의 하위 트리를 결합 할 때주기가없고 두 하위 트리 사이의 최소 비용으로 가장자리를 원하기 때문에 잘라 내기 아이디어를 사용해야합니다. 당신이 이미지에
(D, E)의 비용는 9은 그래서 하위 트리 아닙니다이다. 당신은 평가되지 않은 가장자리라고 생각할 수 있습니다. 하위 트리는 (a, b)이고 (i, c, f, g, h)이므로 잘라내야 이러한 하위 트리를 다른 가장자리와 구별해야합니다.
음영 처리 된 가장자리는 최소한의 비용으로 MST에서 확실한 의미를 나타냅니다. 가장자리 (G, H)는 최소의 비용을 가지고 있기 때문에 먼저 검은을 잘라 얻을 첫 번째 반복에서
: 여기
은 알고리즘의 그림을 그렸다. (g, h) gf가 최소 비용을 가지며이 두 하위 트리가 서로 연결되어 있기 때문에 우리는 하나의 절단을 사용하므로 빨간색 절단이 발생합니다. 등등 ... 더 많이 실행할 수 있기를 바랍니다. Kruskal's 알고리즘이 어떻게 작동하는지 여기에서 볼 수 있습니다.
