MST
스패닝 트리란 그래프에 모든정점을 연결하는 트리이다. 스패닝 트리 중, 트리를 구성하는 간선들의 가중치의 합이 최소가 되는 스패닝 트리가 최소 스패닝 트리가 된다. 정점의 갯수가 V개인 그래프의 최소 스패닝 트리는 V - 1개의 간선을 갖는다. 최소 스패닝 트리를 구하는 알고리즘은 크루스칼 알고리즘, 프림 알고리즘이 있다.
크루스칼
프림
참고
studying
스패닝 트리란 그래프에 모든정점을 연결하는 트리이다. 스패닝 트리 중, 트리를 구성하는 간선들의 가중치의 합이 최소가 되는 스패닝 트리가 최소 스패닝 트리가 된다. 정점의 갯수가 V개인 그래프의 최소 스패닝 트리는 V - 1개의 간선을 갖는다. 최소 스패닝 트리를 구하는 알고리즘은 크루스칼 알고리즘, 프림 알고리즘이 있다.