BFS 인접 리스트

너비 우선 탐색

사용 범위가 DFS에 비해 제한적이다.

길찾기에서 유용하게 쓰인다.

시작점을 지정하고 탐색 시작. 시작점에서 가까운 노드부터 탐색

재귀를 사용하지 않는다. (while 문 사용)

queue 를 사용하여 발견한 노드를 저장

Dfs 는 발견시 바로 해당 노드를 탐색하지만, Bfs 는 발견한 노드를 따로 저장 후 발견한 노드들을 차례대로(선입선출) 탐색한다.

시간 복잡도 :

인접 행렬 : O(n2)

인접 리스트 : O(n+ 간선수)

 

 

시작점이 0노드 일 경우에 1,3 번 노드를 먼저 탐색하고 그 후, 2번 4번 노드를 탐색 한 후 5번 노드를 탐색한다.

여기서 1,3 or 2,4 번 노드 중 어떤 노드에 먼저 탐색을 진행할지는 큐 자료구조를 이용하여 구현한다.

 

인접 리스트를 이용한 Bfs 구현

#include <iostream>
#include <queue>
#include <vector>
#include <list>
using namespace std;

struct Vertex
{
	// int data;
};

vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<vector<int>> adjacent2;
vector<bool> visited;
vector<bool> discovered;

void CreateGraph()
{
	vertices.resize(6);
	discovered.resize(6);

	adjacent = vector<vector<int>>(6);
	adjacent2 = vector<vector<int>>(6);

	// 인접 리스트 사용 그래프 구현
	adjacent[0].push_back(1);
	adjacent[0].push_back(3);
	adjacent[1].push_back(0);
	adjacent[1].push_back(2);
	adjacent[1].push_back(3);
	adjacent[3].push_back(4);
	adjacent[5].push_back(4);

	// 인접 행렬 사용 그래프 구현
	adjacent2 = vector<vector<int>>
	{
		{0,1,0,1,0,0},
		{1,0,1,1,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
	};

}

// 인접 리스트를 이용한 Bfs 구현
void Bfs(int here)
{

	queue<int> q;
	// 발견한 순서를 넣어준다.
	q.push(here);
	// 처음 발견한 노드를 true (탐색했음) 으로 바꾸어준다.
	discovered[here] = true;

	while (q.empty() == false)
	{
		// 다음 방문할 노드 설정 및 큐에서 빼기
		// 여기서 노드 방문하는거
		// 여기서 노드의 데이터 뺄 수 있나?
		here = q.front();
		q.pop();

		cout << "Visited : " << here << endl;

		// DFS 는 다음 탐색할 노드를 발견 후 바로 탐색하지만
		// BFS 는 발견하고 바로 탐색하지 않을 수 있다.
		// 1번 노드가 2,3번 노드를 찾았다 하더라도 3번 노드가 시작노드와 가까우면
		// 2번 노드가 아닌 3번 노드를 탐색해야하기 때문이다.

		for (int there : adjacent[here])
		{
			// 이미 발견한 노드이면 넘어간다
			if (discovered[there])
			{
				continue;
			}

			// 발견되지 않은 코드라면 큐에 넣어준다.
			// 해당 신규 노드가 발견되었음을 알려주기 위해
			// discovered[there] 을 true 로 바꾸어준다.
			q.push(there);
			discovered[there] = true;
		}
	}
}

// 독립된 노드인 5번 노드를 탐색하기 위해서 모든 노드를 시작점으로 for문 돌리기
void BfsAll()
{
	for (int i = 0; i < 6; ++i)
	{
		if (discovered[i] == false)
		{
			Bfs(i);
		}
	}
}

int main()
{
	CreateGraph();

  discovered = vector<bool>(6, false);
	Bfs(0);

	discovered = vector<bool>(6, false);
	cout << "\n";
	BfsAll();
}