데이터 분석 기술 블로그

큐 - BFS(Breadth First Search) 본문

알고리즘

큐 - BFS(Breadth First Search)

데이터분석가 이채은 2024. 6. 11. 09:00

1. BFS (Breadth Frist Search)

  • 그래프를 탐색하는 방법에는 크게 두 가지가 있습니다.
    • 깊이 우선 탐색(Depth First Search, DFS)
    • 너비 우선 탐색(Breadth First Search, BFS)
  • 너비 우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식입니다.
  • 인접한 정점들에대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용합니다. 





연습문제

 

'알고리즘' 카테고리의 다른 글

트리 - 이진트리1  (0) 2024.06.13
트리(Tree)  (2) 2024.06.12
큐 - 버퍼(Buffer)  (0) 2024.06.10
큐 - 우선순위 큐(Priority Queue)  (0) 2024.06.09
큐 - 원형 큐  (0) 2024.06.08