BFS (Breadth First Search) 너비 우선 탐색

BFS (Breadth First Search) 너비 우선 탐색

• 루트 노드나 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 그래프 탐색 방법.

• 시작 정점으로부터 가까운 정점을 먼저 탐색하는 방법이다.

• 따라서 깊게보단 넓게 탐색하기 때문에 너비 우선 탐색이라고 불린다.

• 최단 경로 혹은 임의의 경로를 찾고자 할 때 이 방법을 사용한다.

  • ex) A~Z 의 노드가 있을 경우 A 에서 F 까지의 경로를 찾고자 할 때
  • 깊이 우선 탐색: 최악의 경우 모든 연결 관계를 탐색한다.
  • 너비 우선 탐색: A와 가까운 노드부터 탐색한다.

void Bfs(int here)
{
	// 루트노드를 push하여 탐색 "예약"을 해준다.
	queue<int> q;
	q.push(here);
	discovered[here] = true;

	while (q.empty() == false)
	{
    		// 가장 우선순위로 예약된 노드부터 탐색을 시작한다.
		here = q.front();
        	// 탐색이 실행될 것이니 예약 순위에서 제거한다.
		q.pop();

		cout << "Visited: " << here << endl;
		
        
		for (int there : adjacent[here])
		{
        		// 이미 방문한 노드라면 다시 방문하지 않는다. 
			if (discovered[there])
				continue;
			// 방문한적 없는 노드라면 
            		// 해당 노드에 대한 탐색을 예약한다.
			q.push(there);
           		 // 노드 방문 여부를 true로 처리한다.
			discovered[there] = true;
		}
	}
}

void BfsAll()
{
	// 서로 연결이 안된 정점을 탐색하기 위함
	for (int i = 0;i < 6;i++)
	{
		if (discovered[i] == false)
			Bfs(i);
	}
}

• 시작점과 가까운 정점에 대한 탐색을 Queue에 "예약" 하듯 push를 통해 넣어준다.

• 방문을 했다면 discovered를 true로 하여 무한루프를 방지한다.

• Queue의 선입선출 특징을 이용하여 예약된 순서대로 탐색을 진행한다.

• 몇가지 코드를 추가하면 자신을 발견한 노드에 대한 정보와 시작점에서 얼마만큼 떨어져 있는지에 대한 정보도 알 수 있다.

void Bfs(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 << endl;

		for (int there : adjacent[here])
		{
			if (discovered[there])
				continue;

			q.push(there);
			discovered[there] = true;

			parent[there] = here;
			distance[there] = distance[here] + 1;
		}
	}
}

• 길찾기를 사용할 때 위 Algorithm을 이용하면 distance와 parent를 통해 최단 루트에 대한 정보를 알 수 있다.