알고리즘
[알고리즘] 깊이 우선 탐색(DFS) / 너비 우선 탐색(BFS)
DFS와 BFS는 모두 그래프를 탐색하는 알고리즘이다. 그래프란 노드(Node)과 간선(Edge)로 이루어진 자료구조로, 그래프를 탐색한다는 것은 모든 정점을 방문하는 과정을 의미한다. DFS와 BFS는 이러한 정점을 방문하는 과정에서의 차이로 구분된다. 이 글에서는 DFS와 BFS에 대해 이야기 해볼것이다. 깊이 우선 탐색 (DFS) 이름에서 알 수 있는 DFS는 깊이를 우선한다. 즉, 분기를 만나면 현재 진행 중인 분기를 완전히 깊게 탐색을 마친 후 다음 분기를 탐색한다. DFS는 다음과 같은 특징을 갖는다. 모든 노드를 방문할 때 주로 사용한다. 구현이 BFS보다 간단하다. 검색속도 자체는 BFS보다 느리다. a. 구현 (1) 인접 행렬을 이용한 구현 #include using namespace s..
