프림

트리(Tree) 그래프의 특수한 경우. 사이클이 없이 모든 정점이 연결되어 있는 그래프. 2개의 노드 사이에 반드시 1개의 간선만을 가짐. 부모-자식 관계가 존재하여 계층형 모델이라고도 함. 최상위에 Root 노드 존재. 스패닝 트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 그래프. 그러므로 간선의 개수는 (V-1)개 (V는 정점의 개수) 스패닝 트리 = 신장 트리 최소 스패닝 트리(MST, Minimum Spanning Tree) 스패닝 트리 중 간선 가중치의 합이 최소가 되는 스패닝 트리 MST를 구하는 알고리즘은 보통 아래의 2가지를 많이 사용 크루스칼 알고리즘 (Kruskal Algorithm) 프림 알고리즘 (Prim Algorithm) 크루스칼 알고..