BFS(Breadth-First-Search)

BFS는 너비 우선 탐색

 

그래프에서 순회 방법 중 하나이다.

 

시작 노드에 인접한 노드를 모두 방문하고, 방문한 노드에서 인접 노드를 모두 방문 탐색하는 알고리즘이다.

 

BFS의 동작 과정을 이해하기 위해서는 먼저 그래프 자료구조와 큐 자료구조에 대해 이해할 필요가 있다.

 

BFS 알고리즘은 그래프에서 가까운 노드부터 우선적으로 탐색하는 점에서, 선입선출의 큐(Queue) 자료구조를 활용한다.

인접한 노드를 순차적으로 큐에 삽입하고 (FIFO) 선입선출에 의해 큐를 꺼내도록 알고리즘을 작성하면 된다.

 

---

BFS의 장단점

 

BFS의 장점

 1. 답이 되는 경로의 최단경로를 찾는다.

 2. 무한으로 길어지는 경로의 해답을 찾을 수 있다.

 

BFS의 단점

 1. 경로가 길어짐에 따라 메모리 공간을 많이 차지하게 된다.

 2. 해가 존재하지 않을 경우에 return null 값으로 반환한다.

 3. 무한 그래프의 경우에는 해를 찾지도, 끝을 내지도 못하게 된다.

 

따라서, 이동할때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 생길 경우에는 DFS로 구현하는것이 효율적이다.

 

---

 

BFS 구현

 

큐 (Queue)

 

큐는 탐색 시작 노드 정보를 큐에 삽입하고 방문 처리한다.

큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리한다.

해당 과정을 해를 찾거나 찾지 못할떄까지 반복한다.

 

 

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

#define Max 10

int N, E;
int Graph[Max][Max];

int main()
{
	cin >> N >> E;
	memset(Graph, 0, sizeof(Graph));

	for (int i = 0; i < E; ++i)
	{
		int u, v;
		cin >> u, v;
		Graph[u][v] = Graph[v][u] = 1;
	}

	bfs(0);
	return 0;
}

void bfs(int node)
{
	bool visited[Max] = {false};

	queue<int> myqueue;
	visited[node] = true;
	myqueue.push(node);

	while (!myqueue.empty()) 
	{
		int curr = myqueue.front();
		myqueue.pop();

		cout << curr << ' ';

		for (int next = 0; next < N; ++next)
		{
			if (!visited[next] && Graph[curr][next])
			{
				visited[next] = true;
				myqueue.push(next);
			}
		}
	}
}