dfs1 그래프 탐색 - 깊이 우선 탐색 DFS 그래프의 탐색 혹은 그래프의 순회라고 불리우는 개념은 그래프의 모든 정점을 반드시 한 번은 방문하는 것을 말합니다. 그래프의 탐색 방법에는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 두 종류가 있는 그중에서 깊이 우선 탐색 부터 알아보겠습니다. 1. 깊이 우선 탐색 Depth First Search, DFS 깊이 우선 탐색은 한 정점에서 시작하여 한 방향으로 진행해 갈 수 있는 정점까지 최대한으로 탐색합니다. 그러다가 더이상 진행할 수 없다면 가장 최근에 만난 갈림길이 있는 정점으로 돌아가서 다른 방향의 간선으로 진행할 수 있는지 탐색하는 방식입니다. 깊이 우선 탐색에서는 탐색한 경로의 정보를 담기 위해서 스택을 이용하고, 정점에 대해 방문한 정보를 기록하기 위해서배열을 이용합니다. 말로했을 때.. 2021. 10. 8. 이전 1 다음 300x250
