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

BFS는 그래프를 탐색하는 방법 중 하나로, 너비를 우선적으로 탐색하는 알고리즘이다.

필요한 자료구조: 큐 (First In First Out)

*다음에 방문할 후보를 담아두는 역할

출처: http://mishadoff.com/blog/dfs-on-binary-tree-array/

그림을 보면 그냥 아무 생각 없이 트리라고 생각하기 쉽다.

근데 그래프임. (트리도 그래프에 속하긴 함. 트리와 그래프의 가장 큰 차이는 트리는 사이클이 없음. 트리 탐색은 반복적 순회, 레벨 순회, 이진 탐색 트리 같은 애들이 하는 듯함 )

처음 배울 때 쓴 그래프를 따왔당

얘는 중간에 간선이 더 있어서 트리랑 덜 헷갈린다.ㅎ

출처 : https://blog.naver.com/ndb796/221230944971

전반적인 BFS 내용:

1)

1 값을 갖는 노드를 우선으로 탐색한다고 한다.

1을 방문 표시한다. -> 큐에 push (현재 큐 : 1 && 방문 : 1)

2)

큐의 front 1을 pop 하는데, 이때 1 노드와 연결된 다른 노드를 살펴본다.

2, 3이다.

2, 3을 방문 표시한다 -> 큐에 push (현재 큐 : 2, 3 && 방문: 1, 2, 3)

3)

큐의 front인 2를 pop하는데, 2와 연결된 다른 노드를 살펴본다.

1, 3, 4, 5이다.

이때 1, 3은 방문 표시되어있다.

4, 5를 방문 표시한다 -> 큐에 push (현재 큐 : 3, 4, 5 && 방문: 1, 2, 3, 4, 5)

4)

큐의 front인 3을 pop 하는데, 3과 연결된 다른 노드를 살펴본다.

1, 2, 6, 7이다.

이때 1, 2는 방문 표시되어있다.

6, 7을 방문 표시한다 -> 큐에 push (현재 큐 : 4, 5, 6, 7 && 방문 : 1, 2, 3, 4, 5, 6)

5)

큐의 front인 4를 pop 하는데, 4와 연결된 다른 노드를 살펴본다.

2, 5이다.

2, 5는 모두 방문 표시되어있다. 큐에 넣을 것이 없다. (현재 큐 : 5, 6, 7 && 방문 : 1, 2, 3, 4, 5, 6)

6)

큐의 front인 5를 pop 하는데, 5와 연결된 다른 노드를 살펴본다.

2, 4이다.

2, 4는 모두 방문 표시되어있다. 큐에 넣을 것이 없다. (현재 큐 : 6, 7 && 방문 : 1, 2, 3, 4, 5, 6)

7)

큐의 front인 6을 pop 하는데, 6과 연결된 다른 노드를 살펴본다.

3, 7이다.

3, 7은 모두 방문 표시되어있다. 큐에 넣을 것이 없다. (현재 큐 : 7 && 방문 : 1, 2, 3, 4, 5, 6)

8)

큐의 front인 7을 pop 하는데, 7과 연결된 다른 노드를 살펴본다.

3, 6이다.

3, 6은 모두 방문 표시되어있다. 큐에 넣을 것이 없다. (현재 큐 :  && 방문 : 1, 2, 3, 4, 5, 6)

 

코딩:

조건 :

1. 각각의 간선을 표시해주어야 한다.(간선 정보) -> vector 사용

2. 방문 표시를 해야 한다. -> bool 형태의 visited 배열

3. BFS 구현

vector<int> a[8];

vector를 까먹었었다.ㅎ

그래서 간단하게 vector 개념 

vector <int> a; //1차원이며 동적이다
a.push_back(1) //1을 삽입
a.pop_back() //마지막 제거
a.size() //원소 개수
//등등...

vector <int> a[10]; //2차원이며 동적이다.
//vector <int> a;가 10개 있는 형태
a[0].push_back(1) //a[0][0] = 1;
a[1].push_back(5) //a[1][0] = 5;

 

0. 기본 조건

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

int number = 7; //노드 수가 7
bool visited[8] //방문처리 (인덱스를 1~7로 사용)
vector<int> a[8];

 

1. 각각의 간선을 표시해주어야 한다.(간선 정보) -> vector 사용

int main() {
//1번부터 연결하자 - 2, 3
	a[1].push_back(2);
	a[2].push_back(1);	//양방향 그래프임
    a[1].push_back(3);
    a[3].push_back(1);
    
//2번 연결 - 1, 3, 4, 5 (1은 이미 연결됨)
	a[2].push_back(3);
	a[3].push_back(2);
    a[2].push_back(4);
    a[4].push_back(2);
    a[2].push_back(5);
	a[5].push_back(2);
    
//3번 연결 - 1, 2, 6, 7 (1, 2 제외하고)
	a[3].push_back(6);
	a[6].push_back(3);
    a[3].push_back(7);
	a[7].push_back(3);
    
//4번 연결 - 2, 5 (2 제외)
	a[4].push_back(5);
	a[5].push_back(4);
    
//5번 연결 - 2, 4 (제외)
//6번 연결 - 3, 7 (3 제외)
	a[6].push_back(7);
	a[7].push_back(6);
    
//7번 연결 - 3, 6 (제외)
	bfs(1); //노드 1부터 bfs가 시작되었다
    return 0;
}

간선 정보를 모두 설정했다.

노드 1부터 bfs가 시작되었으므로, 1을 인수로 넘겨주어 본격적인 BFS를 시작한다.

 

2. 방문 표시를 해야 한다. -> bool 형태의 visited 배열

3. BFS 구현

void bfs(int start) {
	queue<int> q;
    visited[start] = true; //큐에 삽입 전 방문 처리
    q.push(start); //큐에 삽입 	
    //둘의 순서는 사실 크게 상관이 없다고))
    
    while(!q.empty()) {
    	int front = q.front(); //front를 꺼낸다
        q.pop();
        printf("%d번 노드 방문 \n", front);
        
        for(int i=0;i<a[front].size();i++) {
        	int node = a[front][i];	 	//연결된 노드를 하나씩 살펴본다
            if(!visited[node]) {	//방문처리가 되지 않았다면
            	visited[node] = true;	//방문처리 후 
                q.push(node);		//큐로
            }
        }
     }
}

 

1학년 때 아무것도 모르고 세미나 들어갔을 땐 그렇게 무시무시해 보였는데 생각보다 재밌는 아이인 것 같다.

근데 백준 풀면 다시 이런 소리 안 할 거 같음ㅋ

 

 

지식 제공자 - 남에게 설명할 줄 알아야 비로소 아는 것이라고 이야기하시는 멘토림