다음 행렬은 그래프(graph)를 인접 행렬(adjacency matr… | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 21년 1회차

다음 행렬은 그래프(graph)를 인접 행렬(adjacency matrix)로 나타낸 것이다. 이 그래프에서 솔린 알고리즘(Sollin algorithm)을 이용하여 최소 비용 신장 트리(minimum spanning tree)를 찾고자 한다. 알고리즘 수행 과정에서 나타나는 부분 그래프에 해당하지 않는 것은? (단, 부분 그래프는 간선의 집합으로 표현하며, 간선은 그래프에 포함된 두 정점 v, k에 대응하여 (v, k)의 형태로 표현한다)
정점 0 1 2 3 4 5 6
0 0 20 15 ∞ ∞ 8 ∞
1 20 0 5 12 ∞ ∞ ∞
2 15 5 0 25 35 28 6
3 ∞ 12 25 0 7 ∞ ∞
4 ∞ ∞ 35 7 0 ∞ 11
5 8 ∞ 28 ∞ ∞ 0 9
6 ∞ ∞ 6 ∞ 11 9 0

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0

{ (0, 5) }

{ (1, 3), (3, 4) }

{ (3, 4) }

{ (1, 2), (2, 6) }

해설

간선 집합 {(1, 3), (3, 4)}는 솔린 알고리즘 수행 중 나타나지 않는다. 트리 {3, 4}에서 밖으로 나가는 최소 간선은 (1, 3)=12가 아니라 (4, 6)=11이어서, (1, 3)은 어느 단계에서도 선택되지 않는다.
1단계(각 정점의 최소 간선): 0·5 → (0, 5)=8, 1·2 → (1, 2)=5, 3·4 → (3, 4)=7, 6 → (2, 6)=6
→ 트리 {0, 5}, {1, 2, 6}, {3, 4}
2단계(각 트리의 최소 간선): {0, 5}와 {1, 2, 6} → (5, 6)=9, {3, 4} → (4, 6)=11
→ 최종: (0, 5), (1, 2), (2, 6), (3, 4), (5, 6), (4, 6)
{(0, 5)}는 1단계에서 정점 0과 5가 고른 간선으로 만들어진 부분 그래프다.
{(3, 4)}는 1단계에서 정점 3과 4가 고른 간선으로 만들어진 부분 그래프다.
{(1, 2), (2, 6)}은 1단계에서 정점 1·2·6이 고른 간선으로 이루어진 부분 그래프다.

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

이어서 풀어보기

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

비슷한 기출

7급 국가직 자료구조론 기출문제 암기장 전체 보기

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0