목록깊이우선탐색 (1)

데이터 분석 기술 블로그

스택 - DFS(깊이우선탐색)

1. DFS(깊이우선탐색)비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요합니다.두 가지 방법으로는 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breadth First Search, BFS)이 있습니다.시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법입니다.가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용합니다.2. DFS 알고리즘 순서1) 시작 정점 v를 결정하여 방문합니다..
알고리즘 2024. 6. 1. 14:10
이전 Prev 1 Next 다음