이번 블로깅에서는 알고리즘에서 자주 나오는 탐색방법인 DFS(깊이우선탐색)과 BFS(너비우선탐색)에 대해 JS 기준으로 한번 쉽게 배워보려 한다.
DFS와 BFS는 탐색 알고리즘 중에 하나이다.
그렇다면 탐색 알고리즘이란 무엇인가?
그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘이다.
당황스러울 수 있다. 그래프는 뭐고 정점은 뭐야,,??
그래프란, 자료구조 중 하나인데 예시를 한번 봐보자.
한 나라에는 도시들이 여러개 존재하고 이들은 도로들이 연결지어주고 있다. 이때 이렇게 도시들과 그에 연결된 도로를 합쳐셔 자료구조로 만든 것이 그래프이다.
이때 정점은 도시들이 되고, 간선은 도로들이 된다.
이제 제대로된 정의를 보자.
그래프는 정점과 간선으로 구성된, 한정된 자료구조를 의미한다.
이때 각각의 지점을 정점이라고 하며, 정점과 정점을 연결지어주는 것을 간선이라고 부른다.
이제 그래프에 대해 이해가 갔을 것이다.
위에 그래프 자료구조를 탐색하는 방법이 DFS, BFS인 것이다.