단순 그래프의 인접 행렬 표현이 인접 리스트 표현보다 점근적으로 빠른 … | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지

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

단순 그래프의 인접 행렬 표현이 인접 리스트 표현보다 점근적으로 빠른 연산으로 옳은 것은? (단, 인접 행렬에서 임의의 정점 v의 행 또는 열의 접근 시간과 인접 리스트에서 임의의 정점 v의 인접 리스트의 접근 시간은 모두 상수이다)

특정 정점의 차수 계산

그래프 전체의 간선 개수 세기

특정 정점에서 시작하는 너비 우선 탐색

특정 두 정점 사이의 간선 존재 여부 확인

해설

인접 행렬이 더 빠른 연산은 두 정점 사이의 간선 존재 여부 확인이다.
인접 행렬은 원소 하나만 보면 되어  $O(1)$ 이지만, 인접 리스트는 한 정점의 리스트를 훑어야 하므로 그 정점의 차수에 비례한다.
특정 정점의 차수 계산은 행렬에서 한 행 전체( $O(n)$ )를 봐야 하고 리스트는 차수만큼만 보면 된다.
전체 간선 개수 세기는 행렬이  $O(n^2)$ , 리스트가  $O(n+e)$ 로 리스트가 유리하다.
너비 우선 탐색도 행렬은  $O(n^2)$ , 리스트는  $O(n+e)$ 로 리스트가 유리하다.

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

이어서 풀어보기

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

비슷한 기출

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

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

→