너비우선탐색(Breadth First Search)
너비우선탐색은 너비를 우선으로 하여 탐색을 수행하는 알고리즘이다.
깊이우선탐색(DFS)와 마찬가지로 맹목적으로 전체노드를 탐색하고자 할 때 자주 사용되며
큐(Queue)자료구조에 기초한다.
너비우선 탐색은 고급 그래프 탐색 알고리즘에서 자주 활용된다.
큐 자료구조에 기초한다는 점에서 구현이 간단하다.
구현함에 있으서 큐STL을 사용하면 좋으며 탐색을 수행함에 있어서 O(N)의 시간이 소요된다.
일반적인 경우 실제 수행시간은 DFS보다 좋은 편이다.
탐색과정
탐색시작 노드를 큐에 삽입하고 방문처리한다.
큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드들을 모두 큐에 삽입하고 방문처리한다.
위 과정을 더이상 수행할 수 없을 때 까지 반복한다.
이와같은 연결리스트가 있고 1부터 시작한다고 했을 때, 큐에 1이 먼저 들어가게 된다.
| 1 |
그리고 1과 인접한 모든 노드를 큐에 넣어주면서 1은 빼준다.
| 2 | 3 | 8 |
그 다음 2와 인접한 노드를 넣어주면서 2를 뺀다.
| 3 | 8 | 7 |
3을 빼면서 3과 인접한 4,5를 큐에 넣는다
| 8 | 7 | 4 | 5 |
8은 인접한 노드가 없으므로 큐에서 빼주기만한다.
| 7 | 4 | 5 |
7을 빼면서 인접노드 6을 큐에 넣는다.
| 4 | 5 | 6 |
4, 5, 6은 방문하지 않은 인접노드가 없으므로 큐에서 빼준다.
그래서 방문순서 즉, 출력순서는
1-2-3-8-7-4-5-6이 된다.
예제코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define INF 99999999
#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];
//정점, 간선, 방문정보
void addFront(Node *root, int index){ //연결리스트 삽입함수
Node *node = (Node*)malloc(sizeof(Node));
node->index = index;
node->next = root->next;
root->next = node;
}
void enQueue(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 deQueue(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;//큐 초기화
enQueue(&q, start);
c[start] = 1;
//방문처리
while(q.count != 0){//큐에 아무것도 없을때까지 반복
int x = deQueue(&q);
printf("%d ", x); //추출한 원소 출력
Node *cur = a[x]->next; //인접한 노드
while(cur != NULL){
int next = cur->index;
if(!c[next]){ //방문하지 않은 상태라면
enQueue(&q, next); //큐에 삽입
c[next] = 1; //방문처리
}
cur = cur->next; //반복을 위해 next
}
}
}
int main(void){
scanf("%d %d", &n, &m);
a = (Node**)malloc(sizeof(Node*) * (MAX_SIZE));
for(int i = 1; i <= n; i++){ //1부터 n까지의 정점에 대해 연결리스트 초기화
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); //노드 1을 기준으로 너비우선탐색 실행
system("pause");
return 0;
}5 4
1 2
1 3
1 5
2 5
이렇게 입력하면
1 5 3 2가 출력된다.
5개의 정점과 4개의 간선이 있도록 하고
각 노드를 만들며 next를 NULL로 초기화한다.
연결리스트에 추가하는 부분을 보면 a[x], y와 a[y], x가 있는데 a[1], 2, a[2], 1 이 형태로 들어간다고 가정하고
처리를 본다면
node->index = 2
node->next = root(a[1])->next(NULL) = NULL
root(a[1])->next = node(index2)
node->index = 1
node->next = root(a[2])->next(NULL) = NULL
root(a[2])->next = node(index1)
이런 식으로 2와 1을 서로 인접한 노드로 만들어주는 것이다.
그림으로 보면 다음과 같다.
1부터 시작한다고 했으니 큐에 처음 1을 넣어준다음 방문처리를 한다.
그리고 반복문으로 큐에 아무것도 남지 않을때까지 반복하도록 하고 큐에 담겨있는 원소를 추출한다.
그럼 제일 먼저 시작 노드인 1이 빠져나오면서 출력되고 1의 인접노드를 cur에 담아 내부 반복문을
수행한다. 내부반복문에서는 해당 노드의 모든 인접 노드를 방문하며 큐에 삽입해주고 방문처리를 한다.
그럼 5, 3, 2순서로 큐에 들어가게 되고 다시 deQueue로 하나 추출한 다음 그 노드의 인접노드를 체크한다.
여기서는 이미 1을 제외한 모든 노드인 5, 3, 2를 다 방문해서 큐에 넣어뒀기 때문에 체크만 하고
하나씩 출력하게 된다.
노드 1의 연결 순서가 5, 3, 2가 되는것은 연결리스트로 처음 들어간 2가 다음에 들어온 3의 next가 되고
3은 그 뒤에 들어온 5의 next가 되기 때문이다.
레퍼런스
패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직
'자료구조' 카테고리의 다른 글
| AVL트리 (0) | 2021.01.17 |
|---|---|
| 이진탐색트리(Binary Search Tree) (0) | 2021.01.16 |
| 깊이우선탐색(DFS) (0) | 2021.01.14 |
| 그래프(Graph) (0) | 2021.01.13 |
| 순차탐색, 이진탐색 (0) | 2021.01.12 |
