Computer Science
-
최소 신장 트리(MST), 크루스칼 알고리즘, 프림 알고리즘Computer Science 2023. 7. 26. 13:12
#최소 신장 트리(MST) 신장 트리 : 무방향 그래프에서 서브 그래프들 중에서 모든 정점을 포함하는 트리 서브 그래프 : 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 그래프 화살표 왼쪽 그래프가 있을 때 화살표 오른쪽 그래프는 왼쪽 그래프의 신장 트리이다. 트리: 무방향이면서 사이클이 없는 연결 그래프 모든 정점을 포함한 서브 그래프이고 트리이므로 오른쪽 그래프는 모두 신장 트리이다. 왼쪽 그래프가 연결 그래프일 때만 신장트리가 존재한다. 오른쪽 그래프는 모두 정점이 N개일 때 N-1개의 간선이 있다는 것을 알 수 있다. 그 이유는 트리의 성질이기 때문이다. 이제 최소 신장 트리에 대해 알아보자 최소 신장 트리는 신장 트리 중에서 간선의 비용 합이 최소인 트리를 말한다. 최소 신장 트리..