-
[알고리즘] BFS(너비 우선 탐색)Problem Solving/자료구조-알고리즘 2025. 4. 23. 06:19
이번 글에서 다뤄볼 내용은 그래프 탐색 기법 중 하나인 BFS(너비 우선 탐색)입니다.
정의
- 그래프에서 어떤 노드에 인접한 노드를 모두 탐색한 뒤, 탐색된 노드를 순서대로 접근하여 인접한 노드를 탐색하는 것을 반복하여 탐색하는 알고리즘
동작 과정
- 현재 노드를 방문처리한다.
- 현재 노드와 연결된 노드 중 방문처리되지 않은 노드를 전부 큐같은 공간에 순서대로 저장한다.
- 저장된 노드 중 가장 첫번째 노드를 현재노드로 하고 큐에서 제거한다.
- 1~3을 그래프의 모든 노드를 탐색할 때까지 반복한다.
구현
// 시간복잡도는 O(노드수 + 간선수)이다. #include <iostream> #include <vector> #include <queue> using namespace std: bool visited[9]; vector<int> graph[9]; void bfs(int start) { queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int x = q.front(); q.pop(); cout << x << ' '; for (int i = 0; i < graph[x].size(); i++) { int y = graph[x][i]; if (!visited[y]) { q.push(y); visited[y] = true; } } } }
이상으로 BFS에 관한 내용을 마치겠습니다.
읽어주셔서 감사합니다.
'Problem Solving > 자료구조-알고리즘' 카테고리의 다른 글
[알고리즘] DFS(깊이 우선 탐색) (0) 2025.04.12 [알고리즘] 에라토스테네스의 체(Eratosthenes Sieve) (0) 2025.04.07 [알고리즘] 누적합(Prefix Sum) (0) 2025.04.02