그래프의 깊이우선탐색에 대한 설명으로 옳지 않은 것은? | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 10년 1회차
그래프의 깊이우선탐색에 대한 설명으로 옳지 않은 것은?
1
그래프의 연결 요소를 구하기 위해 깊이우선탐색을 사용할 수 있다.
2
연결 그래프의 신장트리를 구하기 위해 깊이우선탐색을 사용할 수 있다.
3
최소비용 신장트리를 구하는 Kruskal 알고리즘은 깊이우선탐색을 사용한다.
4
그래프의 임의의 노드에서 깊이우선탐색을 시작할 수 있다.
해설
옳지 않은 것은 Kruskal 알고리즘이 깊이우선탐색을 사용한다는 설명이다.
Kruskal 알고리즘은 간선을 가중치 순으로 정렬해 차례로 고르고, 사이클 여부를 Union-Find(분리 집합)로 판단한다.
- 연결 요소: 방문하지 않은 정점에서 DFS를 반복 시작하면 한 번의 탐색마다 연결 요소 하나를 얻는다.
- 신장트리: 연결 그래프에서 DFS가 지나간 간선들이 깊이우선 신장트리를 이룬다.
- 시작 정점: DFS는 그래프의 어느 정점에서든 시작할 수 있다.
오류나 개정된 내용이 보이면 알려주세요