가치투자자

DFS와 BFS 그래프는 여러 정점(node)과 그 정점들을 연결하는 간선(edge)으로 이루어진 자료구조다. 그래프나 트리 등 비선형 구조로 데이터가 담긴 자료구조는 순차적으로 나열된 선형 구조(배열, 연결리스트, 스택, 큐)에 비해 데이터 탐색이 훨씬 어렵다. 이러한 그래프의 정점들을 처음부터 끝까지 탐색할 때 대표적인 탐색 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. 자주 쓰이는 이 두 가지 알고리즘에 대해 쉽게 설명해보고자 한다. 1. 깊이 우선 탐색 (DFS, Depth First Search) 깊이 우선 탐색 (DFS) 은 가장 깊이 있는(끝에 있는)정점까지 다 탐색하고, 다시 갈림길로 돌아와 다른 길로 끝까지 탐색하는 알고리즘이다. 쉽게 설명하자면, 여러 드라마들이 ..