다음 그래프에서 정점 A를 선택하여 깊이우선탐색(DFS)으로 운행한 결… | 21년-3회차-정보처리기사-필기 기출문제 상세 페이지
121년-3회차-정보처리기사-필기
다음 그래프에서 정점 A를 선택하여 깊이우선탐색(DFS)으로 운행한 결과는?
1
ABECDFG
2
ABECFDG
3
ABCDEFG
4
ABEFGCD
해설
DFS는 A에서 시작해 인접한 B를 먼저 방문한 뒤, B의 미방문 인접정점 E로 내려가고, 이어서 E-F, F-G로 깊이 우선 진행한다. G에서 더 갈 곳이 없으므로 되돌아와(백트래킹) F의 남은 인접정점 C를 방문하고, C와 연결된 D를 마지막으로 방문한다. 따라서 방문 순서는 A→B→E→F→G→C→D가 된다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.