[ 알고리즘 ]
[알고리즘] DFS(Depth-First-Search, 깊이 우선 탐색)
2024-08-13 15:07:20
DFS란? 그래프 탐색 알고리즘으로 그래프의 모든 정점(vertex)을 깊이 탐색하는 방법(알고리즘) DFS는 시작 정점에서 인접한 정점들을 방문하고, 인접 정점들의 인접 정점을 방문하는 방식으로 동작한다.BFS와 다르게 하나의 경로를 깊이(끝)까지 탐색한 후에야 다른 경로로 되돌아와 탐색을 진행한다. 표현 방법// 인접 리스트1 - [2, 8]2 - [1, 3, 6, 7]3 - [2, 4, 5]4 - [3, 5]5 - [3]6 - [2]7 - [2]8 - [1, 9]9 - [8]// 인접 행렬 1 2 3 4 5 6 7 8 91 [0 1 0 0 0 0 0 1 0]2 [1 0 1 0 0 1 1 0 0]3 [0 1 0 1 1 0 0 0 0]4 [0 0 1 0 1 0 0 0 0]5 [0 0 1 1 0 0..