깊이우선탐색

[알고리즘] - DFS & BFS 정리

Graph 그래프는 정점(vertex)과 이들을 연결하는 간선(edge)으로 이루어진 데이터 구조를 말합니다. 그래프는 지도나 인터넷과 같은 물리적인 연결 관계를 나타내기 위해 사용되기도 하지만 그 외 다양한 추상적인 연관성을 나타내기 위해서도 사용됩니다. 이러한 그래프 중 간선에 방향성이 있는 그래프를 방향(direction)이 있다는 의미로 directed graph라 하며, 반대로 간선에 방향성이 없는 그래프를 undirected graph라 합니다. 그래프 탐색 방법에는 대표적으로 2가지가 있습니다. 깊이 우선 탐색인 DFS와 너비 우선 탐색인 DFS가 있습니다. 아래에는 2가지 방법에 대한 설명을 적었습니다. DFS (Depth First Search) - 깊이 우선 탐색 DFS 방법은 root..