크루스칼 알고리즘
-
[56회 변리사 2차-2번] 최소신장트리(MST)알고리즘 2020. 5. 28. 18:01
2019년 제 56회 변리사 2차 데이터 구조론 2교시 2번 문제 해설 MST (Minimum Spanning Tree) 그래프 G에서 모든 정점을 연결하여 갈수 있도록 하되, 최소의 간선개수와 최소의 가중치로 이루어진 트리를 말한다. (즉, 정점 개수 V , 간선 개수 V-1, 간선은 무방향) 1. 그래프 G에 관하여 다음 물음에 답하시오 => 정점(Vertax) 의 개수 8 => 따라서 MST를 만족하는 간선의 개수 (8-1) = 7 개를 선택하면 된다. => 이 그래프에서의 MST가 가지는총 가중치의 합은 10이다. => 즉, 가중치의 합이 10인 MST를 구하는 3가지 알고리즘을 해설 한다. (1) 그래프 G에 대해 프림 알고리즘 (Prim's Algorithm)으로 최소신장트리를 구하는 과정을 ..