#2. 너비 우선 탐색

너비 우선 탐색

 

 

너비 우선 탐색(Breadth First Search)은 너비를 우선으로 하여 탐색을 수행하는 알고리즘이다.

DFS 와 마찬가지로 맹목적으로 전체 노드를 탐생하고자 할 때 자주 사용되며, 큐(Queue) 자료구조에 기초한다.

 

※큐는 차례로 넣고 , 뺄때는 가장 먼저 들어간놈이 빠져 나오는 구조이다.

ex) 1->2->3->4->5 순서대로 넣었다면,  1이 가장 먼저 들어간놈이고, 빠져나올땐 1이 먼저 빠져나간다.

 

너비 우선 탐색 예시(위키백과)

 

위와 같이 전체적으로 크게, 넓게 탐색하는것이 특징이다.

 

장점

1. 출발 노드에서 목표노드까지의 최단 길이 경로를 보장한다.

 

단점

1.경로가 매우 길 경우에는 탐색가지가 매우 넓어지면서, 그에따라 메모리 할당량이 많아진다.

2.해가 존재하지 않는다면, 유한그래프의 경우에는 모든 그래프를 전부 탐색하고나서 실패가 뜬다.

3. 무한 그래프의 경우 해를 찾지도 못하고, 끝내지도 못한다.

 

 

알고리즘 수행과정

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

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

3.반복한다.

 

 

소스코드 예시

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

//연결리스트 정의
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 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);
system("pause");
return 0;
}

#예시

5 4
1 2
1 3
1 5
2 5

 

결과값
1->5->3->2

 

디버깅오류난 부분.

처음에 queuePop 함수를 선언해놓고, bfs함수안에다가는 queuepop함수를 넣어서

디버깅:LNK2019 _queuepop_bfs 함수에서 참조되는 확인할 수 없는 외부 기호  라는 오류가 떴다. 

이는 C언어에서

1.main 함수가 정의되지 않을 때, 발생하는 오류이다.

2.함수의 원형이 있는데 함수의 몸체는 정의되지 않은 상태에서 함수를 호출하면 오류가 생긴다.