[C++ 자/알 Note] BFS 구현

주의사항

- "발견"이라는 개념

DFS는 방문의 개념을 이용했다

BFS는 발견의 개념을 이용한다

 

- 발견 큐

DFS의 핵심은 큐를 이용하는 것이다

발견한 정점들을 큐에 넣어주는 방식을 사용한다

 

- 발견 큐의 구조

일단 큐가 비어있기 때문에

시작 정점을 강제로 큐에 넣어주고 발견 여부를 true로 해주고 시작한다

 

이제 큐가 빌 때까지 큐를 실행하면 된다

큐에 들어있는 본인이 pop 되면서, 발견한 애들을 큐에 넣으면 된다

그리고 방문은 본인이 pop 되는 적절한 시점에 넣어주면 된다

 

- parent와 distance

본인을 발견한 parent를 저장하고 싶은 경우에는

큐에 push를 해주면서 발견여부를 true로 해줄 때

해당 큐를 발견한 정점을 넣어주면 된다

 

- distance

BFS 시작 지점으로부터 거리를 알고 싶은 경우에는

큐에 push를 해주면서 발견여부를 true로 해줄 때

해당 큐를 발견한 정점(부모)의 거리 + 1을 넣어주면 된다

 

BFS 구현

- 준비물

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

 

1) 인접리스트 버전

- 그래프 생성

void CreateGraph_AdjacencyList()
{
	vertices.resize(6);
	adjacent = 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);
}

 

- BFS 한번 실행

void Bfs_AdjacencyList(int here)
{
	// 누구에 의해 발견 되었는지?
	vector<int> parent(6, -1);
	// 시작점에서 얼만큼 떨어져 있는지?
	vector<int> distance(6, -1);

	queue<int> q;
	q.push(here);
	discovered[here] = true;
	parent[here] = here;// parent를 위한 코드
	distance[here] = 0;// distance를 위한 코드

	while (q.empty() == false)
	{
		here = q.front();
		q.pop();

		cout << "Visited: " << here << " Parent: " << parent[here] << " Distance: " << distance[here] << endl;

		for (int i = 0; i < adjacent[here].size(); i++)// for (int there : adjacent[here])// 가능
		{
			int there = adjacent[here][i];

			if (discovered[there] == true)
				continue;

			q.push(there);
			discovered[there] = true;
			parent[there] = here;// parent를 위한 코드
			distance[there] = distance[here] + 1;// distance를 위한 코드
		}
	}
}

 

- BFS 모두 실행

void BfsAll_AdjacencyList()
{
	for (int i = 0; i < 6; i++)
		if (discovered[i] == false)
			Bfs_AdjacencyList(i);
}

 

- 실행

int main()
{
	CreateGraph_AdjacencyList();

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

	//Bfs_AdjacencyList(0);
	BfsAll_AdjacencyList();
}

 

2) 인접행렬 버전

- 그래프 생성

void CreateGraph_AdjacencyMatrix()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6);

	// 인접 행렬
	adjacent = 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},
	};
}

 

- 나머지 부분

인접리스트와의 구현 차이가 있는 부분은

인접한 정점을 순회하는 경우에

연결되지 않은 정점을 걸러내는 부분만 사실상 추가된다

void Bfs_AdjacencyMatrix(int here)
{
	vector<int> parent(6, -1);
	vector<int> distance(6, -1);

	queue<int> q;
	q.push(here);
	discovered[here] = true;
	parent[here] = here;
	distance[here] = 0;

	while (q.empty() == false)
	{
		here = q.front();
		q.pop();

		cout << "Visited: " << here << " Parent: " << parent[here] << " Distance: " << distance[here] << endl;

		for (int i = 0; i < 6; i++)// 달라진 부분
		{
			if (adjacent[here][i] == 0)// 달라진 부분
				continue;

			if (discovered[i] == true)
				continue;

			q.push(i);
			discovered[i] = true;
			parent[i] = here;
			distance[i] = distance[here] + 1;
		}
	}
}