4Legs_Archives

최소 스패닝 트리에 대한 내용과 크루스칼 알고리즘은 아래 포스팅에서 확인할 수 있다. 최소 스패닝 트리 (MST) : 크루스칼 알고리즘 (Kruskal Algorithm) 최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽 4legs-study.tistory.com 프림 알고리즘 (Prim Algorithm) 프림 알고리즘은 최소 스패닝 트리(MST)를 구하는 알고리즘으로, 다음과 같이 동작한다. ① 최초 출발 노드와 연결되어 있는 간선들 중 가중치가 최소인 것을 선택해 MST에 추가한다. 이제 MST에는 2개의 정점이 포함되어..

최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽의 붉은 간선으로 이어진 부분 그래프들은 모두 스패닝 트리에 해당한다. 즉, 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종이므로, V개의 모든 정점을 연결하는 간선의 수는 V - 1개이다. 최소 스패닝 트리(MST)는 이러한 스패닝 트리 중, 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruskal, Prim 알고리즘이 존재한다. 이번 ..