<보기 1>의 인접 행렬로 표현된 그래프 G에 <보기 … | [7급 서울시 자료구조론] 19년 2회차 기출문제 상세 페이지
1[7급 서울시 자료구조론] 19년 2회차
<보기 1>의 인접 행렬로 표현된 그래프 G에 <보기 2>의 알고리즘으로 최소비용신장트리(minimum cost spanning tree)를 생성할 때, 추가되는 간선의 순서로서 옳은 것은? (단, s는 시작 정점을 의미하며, 본 문항에서는 s를 0번 정점으로 한다.)<보기 1>
0 1 2 3 4 5 6 7 8 0 0 3 0 2 0 0 0 0 4 1 3 0 0 0 0 0 0 4 0 2 0 0 0 6 0 1 0 2 0 3 2 0 6 0 1 0 0 0 0 4 0 0 0 1 0 0 0 0 8 5 0 0 1 0 0 0 8 0 0 6 0 0 0 0 0 8 0 0 0 7 0 4 2 0 0 0 0 0 0 8 4 0 0 0 8 0 0 0 0 <보기 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문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요비슷한 기출
- 어느건설공사의한작업이정상적으로시공할때공사기일은10일,공사비는100,000원이고특급으로시공할때공사기일은7일,공사비는30,000원이추가가될때이공사의공기단축시필요97회차(22.11)
- 투상도의배열에사용된제1각법과제3각법의대표기호로옳은것은? {"answer":2,"content":[{"content":"","url":"https:/용접산업기사 4과목 ( 국제 규격 설비 ) 101 ~200번
- 어느토양의양단면적이a1:100엠제곱a2:200엠제곱이고중앙단면적이120엠제곱끝단면부에서중앙단면부까지높이가100m일때양단면적평균법과각주공식에의한토적량은?</p23 1 필생즉사