다음과 같은 그래프에서 Sollin 알고리즘을 사용하여 최소 비용 신장… | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 08년 1회차
다음과 같은 그래프에서 Sollin 알고리즘을 사용하여 최소 비용 신장 트리(minimum cost spanning tree)를 구하려고 한다. Sollin 알고리즘의 시작 단계에서는 하나의 정점으로 이루어진 트리들로 구성된 포리스트(forest)에서 각 트리의 최소 비용 간선(edge)을 선택하게 된다. 하나의 정점으로 이루어진 트리에 대한 최소 비용 간선을 선택할 때, 선택되는 간선이 아닌 것은?
문제 이미지
1
(A, B)
2
(B, E)
3
(C, F)
4
(D, E)
해설

단일 정점 트리들이 고르는 최소 간선은 (A, B), (C, F), (D, E)뿐이므로 (B, E)는 선택되지 않는다.

Sollin 알고리즘 첫 단계에서는 각 정점마다 연결된 간선 중 가중치가 가장 작은 것을 고른다. A와 B는 가중치 5인 (A, B), C와 F는 15인 (C, F), D와 E는 10인 (D, E)를 고른다.

(B, E)의 가중치 20은 B 입장에서는 (A, B)보다, E 입장에서는 (D, E)보다 크므로 어느 쪽에서도 최소가 아니다.

  • (A, B): A와 B 모두의 최소 비용 간선(5)이다.
  • (C, F): C와 F 모두의 최소 비용 간선(15)이다.
  • (D, E): D와 E 모두의 최소 비용 간선(10)이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 08년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기