너비 우선 탐색(Breadth First Search)

너비 우선 탐색(Breadth First Search)

• Vertex 들을 각각 다 한번씩 방문하는데, 넓고 얕게 탐색해 나간다
• Queue 가 사용된다.
• 최단 거리 찾기에 사용할 수 있지만, 간선들의 가중치가 모두 동일할 때만 쓰인다(미로)

 

 

알고리즘 순서

1. Queue에 맨처음 시작 vertex를 넣기
2. 시작 vertex를 방문 처리 해주기
3. Queue 에서 pop(가장 먼저 들어간 vertex) 꺼내기
4. 꺼낸 vertex 에 연결된 vertex 중 방문하지 않은 vertex 들을 방문 처리하고 차례대로 방문 처리한 vertex 들을 queue에 삽입
5. 모두 방문할때 까지 3번, 4번 과정 반복

 

 

BFS를 V0 부터 시작하면, 위 순서대로 방문한다

위 그래프의 인접행렬을 이차원배열로 표현한뒤, BFS또한 구현하여 실행해봤다.

코드

/*
이차원 배열로 그래프의 인접행렬을 표현
배열의 세로축은 정점(vertex)
각각 정점에 대한 가로축 인덱스는 곧 정점 인덱스이며
실제로 들어가는 값은 0 또는 1 이 들어가며  
인접관계에 있어서 true or false를 뜻한다
ex) adj[1][2] //V1 정점과 V2정점과의 인접관계
*/

constexpr int VERTEX_COUNT = 8;
constexpr int adj[VERTEX_COUNT][VERTEX_COUNT] =
{
	{0, 1, 1, 1, 0, 0, 0, 0}, //v0  : v1, v2, v3
	{1, 0, 0, 0, 1, 0, 0, 0}, //v1  : v0, v4
	{1, 0, 0, 0, 0, 1, 1, 0}, //v2  : v0, v5, v6
 	{1, 0, 0, 0, 0, 0, 0, 1}, //v3  : v0, v7
	{0, 1, 0, 0, 0, 0, 0, 0}, //v4  : v1
	{0, 0, 1, 0, 0, 0, 0, 0}, //v5  : v2
	{0, 0, 1, 0, 0, 0, 0, 0}, //v6  : v2
	{0, 0, 0, 1, 0, 0, 0, 0}  //v7  : v3
};

//방문기록을 저장할 배열, 방문하면 true 처리
bool visited[VERTEX_COUNT]; 

void BFS(int _start)
{
	std::queue<int> q; //queue 선언
	q.push(_start); //맨처음 시작 vertex 를 넣기
    visited[_start] = true; //시작 vertex 방문 처리 해주기
	printf("시작 %d 방문\n", _start);
	
    
    //모든 vertex를 방문해서 더이상 queue에 넣을 vertex가 없어서
    //queue가 비어있을 때까지 반복
    while (!q.empty()) 
	{
        //queue에서 가장먼저 넣은 vertex 꺼내기
		int y = q.front(); //queue 에서 front(가장 먼저 넣은 vertex) 값 복사
		q.pop(); //복사 했으니 제거
        
        
		for (int x = 0; x < VERTEX_COUNT; x++)  
		{
			if (adj[y][x] == 0) //인접하지 않으면 skip
			{
				continue;
			}
			else //인접하다면
			{
				//방금꺼낸 vertex 와 인접한 vertex들을 하나씩 가져오기
				if (!visited[x]) //방문했는지 체크, 안했다면
				{
					q.push(x); //queue에 삽입
					visited[x] = true; //방문처리
					printf("%d 방문\n", x);
				}
			}
		}
	}
}

int main()
{
	BFS(0);
	return 0;
}

실행결과

BFS 는 넓고 얕게 탐색해 나간다.

위 콘솔창 실행결과와 오른쪽 그래프를 보면, 화살표 순서대로 실행해 나갔다는것을 알 수 있으며

Breadth First Search(너비 우선 탐색) 알고리즘은 넓고 얕게 탐색해 나간다는 것을 알 수 있다.