알고리즘/BFS

너비 우선 탐색 (BFS, Breadth-First Search) BFS는 그래프의 모든 정점을 탐색하는 알고리즘 가장 가까운 정점부터 우선적으로 탐색하는 방식 특징 재귀적으로 동작하지 않는다 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다 (무한 루프의 위험) 방문한 노드들을 차례대로 저장 한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다 Prim 알고리즘, 다익스트라 알고리즘(Dijkstra’s Algorithm) 과정 설명 시작 정점 선택: 탐색을 시작할 정점을 선택합니다. 인접 정점 큐에 추가: 현재 정점에 인접한 모든 정점을 큐에 추가합니다. 큐에서 정점 추출: 큐에서 정점을 하나씩 추출하며 탐색합니다. 방문..