깊이우선탐색
-어떤 정점을 방문하여 확인한 후 그 정점과 연결된 정점들 중에서 우선 순위가 가장 빠른 하나를 선택해 방문해 나가는데, 더 이상 방문할 곳이 없으면 이전 상태로 되돌아가는 탐색 방법
구현하는 방법
1.순환호출을 이용하는 방법
2.명시적인 스택을 사용하여 인접한 정점들을 스택에 저장하였다가 다시 꺼내는 방법
방문 여부를 기록하기 위해 배열 visited를 사용한다.
그래프가 인접행렬 또는 인접 리스트로 표현되엇는가에 따라 깊이 우선탐색 프로그램이 약간 달라짐
모든 정점의 visited 배열값은 false로 초기화
정점이 방문될 때마다 해당 정점의 visited배열값은 TRUE로 변경
-인접행렬,재귀함수
-인접리스트
- stack 사용
'알고리즘 > 개념' 카테고리의 다른 글
| [알고리즘 문제 해결 전략] 03 알고리즘 설계 패러다임 - 무식하게 풀기 (0) | 2022.08.03 |
|---|---|
| [알고리즘 문제 해결 전략] 02 알고리즘 분석 - 알고리즘의 정당성 증명review (0) | 2022.05.22 |
| [알고리즘 문제 해결 전략] 02 알고리즘 분석 - 알고리즘 시간 복잡도 분석 review (0) | 2022.04.03 |
| 알고리즘 문제해결 전략-01리뷰 (0) | 2022.03.28 |
| 알고리즘 문제해결 전략 (0) | 2022.03.07 |