MST(Minimum Spanning Tree)를 구하는 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘
정보관리기술사 제117회 3교시 22번 문항으로, 과목은 SW공학/프로젝트관리입니다. ‘그리디 알고리즘’ 키워드는 정보관리기술사 기출 2문항에 나왔습니다.
원문 문제
정보관리기술사 제117회 22번. MST(Minimum Spanning Tree)를 구하는 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘
핵심 키워드
- MST
- 크루스칼
- 프림
- 그리디 알고리즘
- 신장 트리
- 간선 선택
- 정점 선택
고득점 가이드 — 1. 개요
최소 신장 트리(MST, Minimum Spanning Tree)는 가중 무방향 그래프의 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되는 트리이다. 크루스칼과 프림은 모두 탐욕(Greedy) 전략에 기반한 대표적 MST 알고리즘이지만, 트리를 확장하는 관점이 서로 다르다.
출제 이력
- MST기출 1문항
- 크루스칼기출 1문항
- 프림기출 1문항
- 그리디 알고리즘기출 2문항
- 신장 트리기출 1문항
- 간선 선택기출 1문항
- 정점 선택기출 1문항