BFS (너비 우선 탐색)

BFS(Breadth First Search)는 시작 위치를 기준으로 가까운 곳 먼저 방문하는 방법이다. 

따라서 시작점에서 얼만큼 떨어져 있는지 탐색하게 되며, 

시작점에서 발견한 순서가 가장 빠른 순으로 해당 vertex에 방문한다. 

 

가중치가 있는 그래프의 경우에는 Dijkistra 알고리즘을 통해 보완해준다. 

(따라서 다음 포스팅은 다익스트라 알고리즘에 대해 알아보려 한다.)

 

DFS와 가장 큰 차이점은 발견 순서와 방문 순서가 동일하다는 점.

BFS는 발견 순서가 빠른 순으로 vertex에 방문하기 때문에

발견 순서와 방문 순서가 동일하다는 특징을 갖는다. 

(DFS는 시작점에서 vertexA와 vertexC를 발견하더라도 먼저 방문한 vertexA에서

다른 vertexB를 발견할 경우, vertexB를 더 우선으로 탐색하는 특징이 있다.)

 

BFS에서는 아래 3가지 정보를 저장할 리스트가 필요하다.

 

1) 발견된 vertex 정보 저장

2) 어떤 vertex에 의해 발견되었는 지 저장 => 최단 경로 파악 시, 활용.

3) 시작 vertex에서 거리가 얼마나 떨어져 있는지 저장

vector<bool> discovered;
vector<int> parent(6,-1);
vector<int> distance(6,-1);

+ 방문할 vertex를 저장할 queue 자료구조도 필요하다

queue<int> visit;

 

왜 queue 자료구조에 저장해줄까??

=> 먼저 발견한 vertex를 먼저 방문해줘야 하니깐!

 

내가 이해한 BFS의 구조는..

방문한 vertex에서 발견한 vertex를 리스트에 넣어준다.

조건 : 발견된 vertex 중 이전에 발견한 적 없는 vertex를 큐(방문할 vertex 목록)에 넣어준다.

이 두 가지가 핵심인 것 같다.. 

 

여기서 '방문하다'라는 의미는 방문할 vertex 목록인 큐에서 빼주는 것을 의미한다.

 

1. 그래프 생성

  * dfs에서 예시로 들었던 그래프와 동일하다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> graph;

void CreateGraph()
{
	graph.resize(6);

	graph[0] = { 1,3 };
	graph[1] = { 0,2,3 };
	graph[3] = { 4 };
	graph[5] = { 4 };
	
}

 

2. BFS 코드 작성

vector<bool> discovered(6, false);

void BFS(int here)
{
    vector<int>distance(6, -1);
    
    queue<int> visit;
    
    discovered[here] = true;
    distance[here] = 0;
    
    visit.push(here);
    
    while(visit.empty()==false)
    {
        int vertex = visit.front();
        visit.pop();
        
        for(int val : graph[vertex])
        {
            if(discovered[val])
                continue;
            
            disatance[val] = distance[vertex]+1;
            discovered[val] = true;
            visit.push(val);
        }
    }
}

 

모든 vertex를 방문하려면?

=> 방문한 적 없는 vertex를 시작점으로 삼고, 다시 bfs 코드 실행.

void bfs_all()
{
	for (int i = 0; i < discovered.size(); i++)
	{
		if (!discovered[i])
		{
			bfs(i);
		}
	}
}