다음 그래프에서 프림 알고리즘(Prim algorithm)을 사용하여 … | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 23년 1회차
다음 그래프에서 프림 알고리즘(Prim algorithm)을 사용하여 최소 비용 신장 트리를 만들 때, 트리에 네 번째로 포함되는 간선은? (단, 시작 정점은 0이다)
1
(0, 1)
2
(1, 4)
3
(2, 3)
4
(4, 5)
해설
시작 정점 0에서 프림 알고리즘을 적용하면 네 번째로 추가되는 간선은 (1, 4)이다.
트리에 인접한 간선 중 최소 가중치를 차례로 고르면 (0, 2) 1 → (2, 1) 2 → (0, 3) 3 → (1, 4) 7 → (4, 5) 4 순이다.
세 간선을 추가한 뒤 트리는 {0, 1, 2, 3}이고, 바깥으로 나가는 후보는 (1, 4) 7, (2, 4) 8, (3, 5) 9뿐이어서 가중치 7인 (1, 4)가 선택된다.
- 간선 (0, 1)은 두 정점이 이미 트리에 있어 사이클을 만들므로 선택되지 않는다.
- 간선 (2, 3)도 두 정점이 이미 트리에 포함되어 사이클을 만든다.
- 간선 (4, 5)는 정점 4가 트리에 들어온 뒤 다섯 번째로 추가된다.
오류나 개정된 내용이 보이면 알려주세요