다음 그래프를 Kruskal 알고리즘을 이용하여 최소 비용 신장 트리로… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 19년 1회차
다음 그래프를 Kruskal 알고리즘을 이용하여 최소 비용 신장 트리로 만들 때 선택되지 않는 간선은? (단, 알고리즘은 노드 A에서 시작한다)
문제 이미지
1
(A, C)
2
(B, C)
3
(B, F)
4
(C, D)
해설

Kruskal 알고리즘에서 선택되지 않는 간선은 (C, D)이다.

가중치가 작은 간선부터 사이클이 생기지 않으면 채택한다. (A, D)=1, (A, C)=2를 고른 뒤 (C, D)=3은 A–C–D 사이클을 만들므로 버린다.

이어서 (D, E)=4를 채택하고 (C, E)=5는 사이클이라 버리며, (B, C)=6, (B, F)=7을 채택하면 정점 6개에 간선 5개로 신장 트리가 완성된다.

  • (A, C)는 가중치 2로 두 번째에 채택된다.
  • (B, C)는 가중치 6으로 B를 트리에 연결하며 채택된다.
  • (B, F)는 가중치 7로 마지막에 F를 연결하며 채택된다.

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

이어서 풀어보기

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