Breadth-First-Search

Breadth-First Search

• 넓이 우선 탐색
• 트리, 그래프 탐색의 대표적인 알고리즘으로 레벨탐색이라고도 불린다.
• 부모노드의 연결된 자식노드를 모두 탐색한 후 다시 자식노드의 연결된 다음 레벨의 자식노드를 탐색하는 방식이다.
• DFS(깊이우선탐색)과 반대로 넓이를 먼저 탐색하고 다음 레벨을 탐색하는 완전탐색방법이다.
• DFS에서는 스택 자료구조를 사용하지만 BFS는 큐를 사용한다.

사용한 자료구조

• 큐
  • First In First Out(선입선출 방식의 데이터 구조로 먼저 들어간 데이터를 먼저 삭제하는 자료구조)

위와 같이 이진트리가 주어졌을 때 BFS 그래프 탐색을 구현해 보았다.

• 우선 이진트리는 C++의 vector 자료구조를 활용해 인접리스트 방식으로 구현한 후 1번 노드 부터 탐색을 진행하도록 코드를 구현했다.
• front와 rear변수만으로 간단하게 직접 구현한 큐를 구현해서 사용했다.(rear를 통해서만 큐에 enque하고 front를 통해서만 deque하도록 했다.)
• 시작 노드인 1번 노드를 queue에 넣어준 후 여기부터 탐색을 진행했다. 탐색 종료 조건은 큐가 비었을 때 까지 진행하는데 front와 rear가 같게 되면 큐는 비어 있는 상태이므로 front<rear라면 queue에 데이터가 들어가 있는 경우 이므로 while문의 조건을 front<rear라고 주었다.
• 이렇게 큐에 데이터가 모두 빠지기 전까지 front에 있는 데이터를 제거하고 제거한 데이터(x)와 연결된 자식노드를 방문한다. 연결된 자식노드는 인접리스트 방식으로 map[x]의 사이즈 만큼 map[x]에 연결된 데이터가 방문한적 있는지 체크한 후 방문한 적이 없다면 큐에 넣어주고 방문체크를 해준다.
• 위와 같은 방식으로 큐에 데이터가 모두 빠질때 까지 완전탐색을 진행한다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int Q[100], front=-1, rear=-1, visited[10];
vector<int> map[10];

int main(){
    //freopen("input.txt", "rt", stdin);
    int i, a, b, x, firstX= 1;
    for(i=1; i<=6; i++){
        scanf("%d %d", &a, &b);
        map[a].push_back(b);
        map[b].push_back(a);
    }

    //Queue에는 rear부터 넣어준다.    
    Q[++rear] = firstX;
    visited[firstX] = 1;

    while(front<rear){
        x=Q[++front];
        printf("%d ", x);
        //x에 연결된 부분을 저장해두었던 인접리스트로 표현해 2차원 vector에 각 노드에 연결된 사이즈 만큼 for문으로 확인
        for(i=0; i<map[x].size(); ++i){
            printf("%d ",map[x][i]);

            //queue에서 빼준(queue에는 가장 먼저들어 간 순서대로 빠진다.) 노드에 연결된 부분을 순차적으로 방문확인하고
            //방문 하지 않았으면 방문처리하고 Queue에 넣어준다.
            if(visited[map[x][i]] == 0){
                visited[map[x][i]] = 1;
                Q[++rear] = map[x][i];
            }
        }
        printf("\n");
    }
    return 0;
}