• 그래프를 완전 탐색하는 방법 중 하나
• 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

• Queue 자료구조 이용 | O(V + E) |

• 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장

핵심 이론

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입

3. 큐 자료구조에 값이 없을 때까지 반복

[026] DFS와 BFS 프로그램

• https://www.acmicpc.net/problem/1260
• 노드를 기준 → 인접 리스트에 그래프를 저장
• 에지를 기준 → MST(Minimum Spanning Tree), 벨만-포드 → 에지 리스트로 구현
• 먼저 오름차순으로 정렬