<보기 1>의 인접 행렬로 표현된 그래프 G에 <보기 … | [7급 서울시 자료구조론] 19년 2회차 기출문제 상세 페이지

1[7급 서울시 자료구조론] 19년 2회차
<보기 1>의 인접 행렬로 표현된 그래프 G에 <보기 2>의 알고리즘으로 최소비용신장트리(minimum cost spanning tree)를 생성할 때, 추가되는 간선의 순서로서 옳은 것은? (단, s는 시작 정점을 의미하며, 본 문항에서는 s를 0번 정점으로 한다.)
<보기 1>
012345678
0030200004
1300000040
2000601020
3206010000
4000100008
5001000800
6000008000
7042000000
8400080000
<보기 2>
MST(G, s)
{
1. 그래프 G에서 시작 정점 s를 가지고 초기 신장 트리를 만듦
2. 현재 트리의 정점들과 인접한 정점들 중에서 간선의 가중치가
가장 작은 정점 v를 선택
3. 선택된 정점 v와 간선을 신장 트리에 추가 (단, 사이클(cycle)
이 발생하지 않아야 함)
4. 현재 신장 트리에 모든 정점이 포함되지 않았다면 2번 단계로
이동
}
1
(0, 3), (3, 4), (4, 8), (3, 2), (2, 7), (7, 1), (2, 5), (5, 6)
2
(0, 3), (3, 4), (0, 1), (1, 7), (7, 2), (2, 5), (0, 8), (5, 6)
3
(0, 3), (0, 1), (0, 8), (1, 7), (7, 2), (2, 3), (2, 5), (5, 6)
4
(0, 3), (3, 4), (0, 8), (0, 1), (1, 7), (7, 2), (2, 5), (5, 6)
해설
등록된 해설이 없습니다.

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

이어서 풀어보기

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