728x90 반응형 최단 경로 탐색1 그래프 탐색하기 위한 대표적인 알고리즘 DFS/BFS - BFS란? 1. BFS (Breadth First Search)BFS는 '너비 우선 탐색' 알고리즘으로, 가까운 노드부터 탐색하는 방식이다.DFS가 깊이 우선으로 탐색하는 것과 달리, BFS는 탐색 시작 노드에서 가까운 노드를 먼저 방문하고 점점 멀리 있는 노드를 방문한다. BFS의 구현에서는 선입선출(FIFO) 구조인 큐(Queue)를 사용한다. 인접한 노드를 큐에 삽입하면, 먼저 들어온 노드가 먼저 처리되므로 가까운 노드부터 탐색하게 된다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.큐에서 노드를 꺼내고, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 아래 그래프에서 노드 1을 시작 노드로 BFS.. 2025. 2. 10. 이전 1 다음 728x90 반응형
