Breadth-first search (너비 우선 탐색) 정리 및 구현(C++)

📝목차

1. Breadth-first search(BFS) 소개 2. BFS 특징 3. BFS 동작과정 4. BFS C++구현

 

---

 

1. Breadth-first search(BFS) 소개

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

출처 https://developer-mac.tistory.com/64

트리나 그래프에서 하나의 정점에서 시작해서 인접한 정점부터 탐색하는 알고리즘이다. 더 이상 방문할 정점이 없을 때까지 반복한다.

주로 두 노드사이의 최단경로를 구하거나, 특정도시에서 다른 도시로 갈 수 있는지 탐색하는 알고리즘이다.

 

 

2. BFS 특징

1️⃣ 시작노드로부터 가까운 정점을 먼저 방문한다.

2️⃣ 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.

3️⃣ 선입선출(FIFO)원칙으로 탐색하기 때문에 큐(Queue)를 사용한다.

4️⃣ Prim’, ‘Dijkstra’ 알고리즘과 유사하다.

5️⃣ 재귀적으로 동작하지 않는다 (DFS는 재귀 호출 이용)

6️⃣ 경로가 길 경우, 탐색 가지가 급격히 증가함에 따라 많은 기억 공간이 필요하다.

 

 

 

3. BFS 동작과정

1️⃣ 루트 노드 정보를 큐에 삽입하고 방문 처리를 한다.

2️⃣  큐에서 노드를 꺼낸 후, 꺼낸 노드와 방문하지 않은 인접 노드 정보를 모두 큐에 넣는다.

3️⃣  2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

💬

 

 

 

STEP 0. 시작노드 1 방문처리 후 큐에 삽입(생략)

 

 

STEP1. 큐에서 1번 노드 꺼내 방문하지 않은 인접노드 2, 5, 6, 3  큐에 넣고 방문 처리

 

 

STEP2. 큐에서 2번 노드 꺼내 방문하지 않은 인접노드 4  큐에 넣고 방문 처리

 

STEP3. 큐에서 5번 노드 꺼내 방문하지 않은 인접노드 8  큐에 넣고 방문 처리

 

STEP4. 큐에서 6번 노드 꺼내 방문하지 않은 인접노드 9  큐에 넣고 방문 처리

 

STEP5. 큐에서 3번 노드 꺼내고 방문하지 않은 인접노드가 없어 continue

 

STEP6. 큐에서 4번 노드 꺼내 방문하지 않은 인접노드 7 큐에 넣고 방문 처리

 

STEP7. 큐에서 8번 노드 꺼내고 방문하지 않은 인접노드가 없어 continue

9,7도 똑같은 과정 반복하니 생략

 

 

✔️ 탐색순서 : 1 > 2 > 5> 6 > 3 > 4 > 8 > 9 > 7

 

 

3. BFS C++ 구현

#include <bits/stdc++.h>
using namespace std;
bool visited[9]; //방문 여부
vector <int> graph[10]; // 그래프

void bfs(int start) {
	queue<int> q;
	q.push(start); // 첫 노드 queue에 삽입
	visited[start] = true; // 첫 노드 방문 처리

	while (!q.empty()) {
		// 큐가 비면 break
		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; // 방문처리
			}
		}
	}
}

int main() {

	// 노드1에 연결된 노드 정보 저장
	graph[1].push_back(2);
	graph[1].push_back(5);
	graph[1].push_back(6);
	graph[1].push_back(3);

	// 노드2에 연결된 노드 정보 저장
	graph[2].push_back(1);
	graph[2].push_back(4);

	// 노드4에 연결된 노드 정보 저장
	graph[4].push_back(7);
	graph[4].push_back(7);

	// 노드5에 연결된 노드 정보 저장
	graph[5].push_back(1);
	graph[5].push_back(8);

	// 노드6에 연결된 노드 정보 저장
	graph[6].push_back(1);
	graph[6].push_back(9);

	// 노드7에 연결된 노드 정보 저장
	graph[7].push_back(4);
	graph[7].push_back(8);

	// 노드8에 연결된 노드 정보 저장
	graph[8].push_back(5);
	graph[8].push_back(7);

	// 노드9에 연결된 노드 정보 저장
	graph[9].push_back(6);

	bfs(1); // 1번 노드부터 시작
	return 0;
} //main

 

output:

 

 

---

참고

 

https://www.youtube.com/watch?v=CJiF-muKz30 

https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

DFS & BFS 이해하기 및 구현(C++)

https://hongku.tistory.com/156

알고리즘 :: BFS 너비 우선 탐색 (C/C++ 구현), 탐색알고리즘

https://heytech.tistory.com/56

[Python] BFS 알고리즘 개념 및 실습