[DS] 넓이 우선 탐색(BFS)이란?

하나의 vertax로부터 모든 vertex를 한 번씩 방문하는 그래프 탐색이 있습니다.

 

 

↓↓↓       그래프란?      ↓↓↓

https://yyyeji.tistory.com/378

[DS] 그래프(Graphs)의 종류와 관련 용어

 

 

 

아래에 BFS 방문 예제와 코드가 있습니다.

깊이 우선 탐색(Depth First Search)이란?

그래프 탐색에서 넓이 부분을 먼저 탐색하는 알고리즘이며,

큐(queue)를 사용합니다.

 

 

↓↓↓        큐(queue)?     ↓↓↓

https://yyyeji.tistory.com/364

[DS] 큐(Queue)란?

 

 

 

장점(Adventage)

---

시작되는 vertex에서 가고자 하는 목표까지 최단 길이의 경로를 보장합니다.

 

 

 

알고리즘(Algorithm)

---

① 시작할 vertex를 방문하고, 큐(queue)에 넣는다.

② 큐(queue)에 front와 인접(adjacent)한 vertex 중에 아직 방문하지 않은 vertex를 한 개 선택하여 방문하고 큐(queue)에 넣는다.

③ 더 이상 선택할 원소가 없다면, 큐(queue)에서 원소 하나를 제거(delete)합니다.

 

큐(queue)이 빈(empty) 상태일 때까지 ②~③번을 반복합니다.

 

 

아래 그래프의 모든 vertex를 넓이 우선 탐색을 통해 방문해 보겠습니다.

 

 

ⓐ를 시작 vertex로 두겠습니다.

ⓐ
front

ⓐ에서 방문할 수 있는 vertex는 ⓑ, ⓒ입니다.

 

 

ⓑ, ⓒ 모두 방문한 후 큐(queue)에 넣어줍니다.

ⓐ	ⓑ	ⓒ
front		rear

ⓐ에서 방문할 수 있는 vertex는 모두 방문했기 때문에 

 

 

front 원소를 하나 제거(delete)해줍니다.

	ⓑ	ⓒ
	front	rear

ⓑ에서 방문할 수 있는 vertex에 방문합니다.

 

 

	ⓑ	ⓒ	ⓓ	ⓔ
	front			rear

모두 방문했다면 ⓑ를 제거(delete)합니다.

 

 

		ⓒ	ⓓ	ⓔ
		front		rear

ⓒ에서 방문할 수 있는 vertex에 방문하고 큐(queue)에 넣어줍니다.

 

 

		ⓒ	ⓓ	ⓔ	ⓕ
		front			rear

방문이 완료되었다면 ⓒ를 제거(delete)하고 front 원소에서 방문할 수 있는 vertex에 모두 방문합니다.

 

 

			ⓓ	ⓔ	ⓕ	ⓖ
			front			rear

ⓓ에서 방문할 수 있는 vertex를 방문했다면 ⓓ를 제거(delete)하고 front 원소에서 방문할 수 있는 vertex에 모두 방문합니다.

 

 

				ⓔ	ⓕ	ⓖ	ⓗ
				front			rear

모든 vertex를 방문했기 때문에 큐(queue)에 남아있는 원소를 모두 제거(delete)하면 됩니다.

 

 

 

 

재귀함수 함수 구현

---

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

bool visited[8];
vector<char> graph[8];

void bfs(char start) {
    queue<char> q;
    q.push(start);

    visited[start] = true;
    while(!q.empty()) {
        char s = q.front();
        q.pop();
        cout<< s << " ";

        for(int i = 0; i<graph[s].size(); i++) {
            char y = graph[s][i];

            if(!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

visited[8]는 vertex 방문 여부를 위한 배열입니다.

vector<char> graph[8]은 그래프의 정보를 담고 있을 벡터(vactor)입니다.

 

사용자 정의 함수인 bfs()를 살펴보겠습니다.

 

queue<char> q;

char 타입의 queue를 하나 생성해 줍니다.

 

q.push(start);

파라미터(parameter)로 들어온 문자를 큐(queue)에 넣어줍니다.

 

visited[start] = true;

파라미터(parameter)로 들어온 문자의 vertex를 지금 방문했기 때문에 visited를 true로 바꿉니다.

 

while(!q.empty()) {

q가 빈(empty) 상태일 때까지 다음을 반복합니다.

 

char s = q.front();

front 원소를 하나 알아내고

 

q.pop()

front 원소를 제거(delete)해줍니다.

 

cout << s << " ";

방금 pop된 원소를 출력합니다.

 

for(int i = 0; i<graph[s].size(); i++) {

한 vertex에 연결된 다른 vertex에 모두 방문하게 됩니다.

 

char y = graph[s][i];

현재 vertex에 연결된 한 vertex를 가져옵니다.

 

if(!visited[y]) {

가져온 vertex가 아직 방문되지 않았다면 

 

q.push(y);

큐(queue)에 넣어주고

 

visited[y] = true;

방문 체크도 해줍니다.

 

 

main 함수 구현

---

int main() {
    graph['a'].push_back('b');
    graph['a'].push_back('c');

    graph['b'].push_back('a');
    graph['b'].push_back('d');
    graph['b'].push_back('e');

    graph['c'].push_back('a');
    graph['c'].push_back('f');

    graph['d'].push_back('b');
    graph['d'].push_back('g');

    graph['e'].push_back('b');
    graph['e'].push_back('h');

    graph['f'].push_back('c');
    graph['f'].push_back('h');

    graph['g'].push_back('d');
    graph['g'].push_back('h');

    graph['h'].push_back('g');
    graph['h'].push_back('e');
    graph['h'].push_back('f');

    bfs('a');

    return 0;    
}

위에서 풀었던 BFS 예제와 같이 그래프를 생성해주었습니다.

 

 

main 함수를 실행하면 아래와 같은 벡터(vector)가 생성됩니다.

위에 있는 예제와 같이 따라갔을 때 결과가 잘 출력된 것을 확인할 수 있습니다.

 

 

↓↓↓       다른 그래프 탐색 방법 공부하기     ↓↓↓

https://yyyeji.tistory.com/379

[DS] 깊이 우선 탐색(DFS)이란?

 

 

 

◡̈