목록BFS (1)

FE PARADISE

[알고리즘] BFS 너비 우선 탐색 - 자바스크립트 코드 포함 간략한 설명

너비 우선 탐색 (BFS, Breadth-first search) 시작 정점에서 시작하여 인접한 모든 정점을 방문하는 방법이다. 재귀호출을 사용하는 DFS와 다르게 자료 구조 큐 Queue를 사용하는 방식이 일반적이다. 정점에 연결되는 모든 갈림길을 탐색을 하다보니 어떠한 시작점과 끝점이 주어졌을때 그 둘 사이의 최단 거리 구하기에 용이하다. 아래 그림을 보며 살펴보자. 그림에선 시작 정점을 ㄱ으로 본다. 시작 정점을 기준으로 인접한 정점은 ㄴ,ㄷ,ㄹ이다. 그리하여, ㄴ,ㄷ,ㄹ 정점을 방문한다. 그 후, ㄴ에 인접한 ㅁ,ㅂ,ㅅ 정점을 방문하고, ㄷ,ㄹ도 마찬가지로 인접한 정점을 차례대로 방문한다. DFS와 달리 너비를 기준으로 순회하는 방식이다. 다음 그림의 트리를 너비 우선 탐색으로 순회하여 값을 프린..
자료구조 & 알고리즘 2023. 11. 14. 01:17
이전 Prev 1 Next 다음