그래프의 깊이우선탐색에 대한 설명으로 옳지 않은 것은? | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 10년 1회차
그래프의 깊이우선탐색에 대한 설명으로 옳지 않은 것은?
1
그래프의 연결 요소를 구하기 위해 깊이우선탐색을 사용할 수 있다.
2
연결 그래프의 신장트리를 구하기 위해 깊이우선탐색을 사용할 수 있다.
3
최소비용 신장트리를 구하는 Kruskal 알고리즘은 깊이우선탐색을 사용한다.
4
그래프의 임의의 노드에서 깊이우선탐색을 시작할 수 있다.
해설

옳지 않은 것은 Kruskal 알고리즘이 깊이우선탐색을 사용한다는 설명이다.

Kruskal 알고리즘은 간선을 가중치 순으로 정렬해 차례로 고르고, 사이클 여부를 Union-Find(분리 집합)로 판단한다.

  • 연결 요소: 방문하지 않은 정점에서 DFS를 반복 시작하면 한 번의 탐색마다 연결 요소 하나를 얻는다.
  • 신장트리: 연결 그래프에서 DFS가 지나간 간선들이 깊이우선 신장트리를 이룬다.
  • 시작 정점: DFS는 그래프의 어느 정점에서든 시작할 수 있다.

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

이어서 풀어보기

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