목록2025/02/24 (1)

데이터 분석 기술 블로그

너비 우선 탐색 (BFS, Breadth-First Search)

너비 우선 탐색 BFS"그래프 탐색 기법 중 하나로, 가까운 노드부터 차례대로 탐색하는 방식"큐(Queue)를 사용하여 구현한 단계씩 확장하며 탐색 → 최단 경로 문제에서 유용함DFS(깊이 우선 탐색)와 달리, 모든 노드를 동일한 깊이(레벨)에서 먼저 탐색BFS 동작 원리시작 노드를 큐(Queue)에 삽입하고 방문 처리큐에서 노드를 꺼내고, 인접한 노드를 모두 큐에 삽입큐가 빌 때까지 위 과정을 반복# Pseudo CodeFUNCTION DFS(node): 방문[node] = True # 현재 노드를 방문 처리 출력(node) # 노드 방문 FOR 모든 인접 노드 in node의 이웃 리스트: IF 방문[인접 노드] == False THEN DFS(인접..
데이터 사이언스/알고리즘 2025. 2. 24. 13:49
이전 Prev 1 Next 다음