목록2024/07/07 (1)

데이터 분석 기술 블로그

DFS

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