[자료구조] 너비 우선 탐색(BFS)

너비우선탐색(BFS= Breadth First Search) 는 너비를 우선으로 탐색하는 알고리즘입니다. 기본적으로 큐(Queue)를 이용하여 구현합니다. 

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다 

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드들을 모두 큐에 삽입하고, 방문 처리를 합니다 .

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다. 

 

큐에 첫번째 노드 1을 넣고, 다음으로는 노드1과 연결된 노드 2,3,4 를 넣는다. 더이상 노드 1과 연결된 노드가 없으므로 노드 2와 연결된 노드 5,6을 넣고 마지막으로 노드 6과 연결된 노드 7을 넣는다.

 

너비 우선 탐색은 큐(Queue)자료구조에 기초한다는 점에서 구현이 간단합니다. 실제로 구현함에 있어 큐 STL을 사용하면 좋으며 탐색을 수행함에 있어서 O(N)시간이 소요됩니다. 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편입니다. 

 

#include <stdio.h>
#include <stdlib.h>
#define INF 999999999
#define MAX_SIZE 1001

typedef struct{
	int index;
    struct Node *next;
} Node;

typedef struct{
	Node *front;
    Node *rear;
    int count;
} Queue;

Node++ a;
int n, m, c[MAX_SIZE]; //배열 c는 방문한 정보

void addFront(Node *root, int index){
	Node *node = (Node*)malloc(sizeof(Node));
    node->index = index;
    node->next = root->next;
    root->next = node;
}

void queuePush(Queue *queue, int index){
	Node *node = (Node*)malloc(sizeof(Node));
    node->index = index;
    node->next = NULL;
    if(queue->count == 0){   //현재 큐가 비어있으면
    	queue->front = node; //앞에 삽입
    }else{
    	queue->rear->next = node; //뒤에 삽입
    }
    queue->rear = node;
    queue->count++;
}

int queuePop(Queue *queue){
	if(queue->count == 0){   //꺼낼 노드가 없을 때 
    	printf("큐 언더플로우 발생\n");
        return -INF; 
    }
    Node *node = queue->front;
    int index = node->index;
    queue->front = node->next;
    free(node);
    queue->count--;
    return index;
}

void bfs(int start){
	Queue q;
    q.front = q.rear = NULL;
    q.count = 0;
    queuePush(&q, start);
    c[start] = 1;
    while(q.count!=0){  //큐가 빌 때까지 반복
    	int x = queuePop(&q);
        printf("%d ",x);
        Node *cur = a[x]->next;
        while(cur!=NULL){
        	int next = cur->index;
            if(!c[next]){     //해당 인접 노드가 방문하지 않은 상태라면
            	queuePush(&q, next);
                c[next] = 1;  //방문
            }
            cur = cur->next;
        }
    }
}

int main(void){
	scanf("%d %d", &n, &m);
    a = (Node**)malloc(sizeof(Node*) * (MAX_SIZE));
    for(int i=1; i<=n; i++){
    	a[i] = (Node*)malloc(sizeof(Node));
        a[i]->next = NULL;
    }
    for(int i=0; i<m; i++){
    	int x, y;
        scanf("%d %d", &x, &y); //간선의 갯수만큼 입력받는다
        addFront(a[x], y);
        addFront(a[y], x);
    }
    bfs(1);
    return 0;
}