다음 그래프에 대해 정점 A를 시작으로 프림(Prim) 알고리즘을 수행… | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지

생성된 최소 신장 트리의 간선은 5개이다.
신장 트리는 모든 정점을 사이클 없이 연결하므로 정점이 n개이면 간선은 n − 1개이다. 그래프의 정점은 A~F의 6개이므로 간선은 5개가 된다.
실제로 A에서 프림 알고리즘을 수행하면 A-B(2), B-F(1), B-E(3), E-D(2), B-C(4)를 차례로 선택해 총 가중치 12의 트리가 만들어진다.
4개: 간선이 4개이면 정점 6개를 모두 연결할 수 없다.
6개: 정점 6개에 간선을 5개보다 많이 두면 반드시 사이클이 생겨 트리가 아니다.
7개: 간선 수를 정점 수보다 크게 센 것으로, 정점 6개의 신장 트리는 간선이 항상 5개로 고정된다.