안녕하세요 c++ 공부하고있는 대학생입니다.
이번에는 bfs에 대하여 정리하고자 합니다.
BFS 란? root노드로부터 인접한 노드 먼저 탐색하는 방법
BFS를 구현하기에 앞서 알아두어야 할 사항이 몇가지 있습니다.
- 시작점으로부터 가까운 점 먼저 방문하고 멀리떨어진 점을 나중에 순회한다.
- 두 노드 사이간 최단경로 또는 찾고자하는 경로가 있을 때 BFS를 사용한다.
- 반드시 노드를 방문 할 시, 방문했다는 체크를 해야한다.
- 자료구조 중 큐를 써야한다.
이렇게 4가지로 나눌 수 있습니다.
예시로 보여드리겠습니다.
이렇게 노드간 연결이 되었다고 가정을 하고, (root 노드는 1입니다.)
과정을 설명드리자면,
- 먼저 1을 방문하고 방문에 대한 체크를 해 줍니다. 그리고 큐에 넣습니다.
- 그 다음 2와 3을 차례대로 방문하고, 1을 큐에서 반환 해 주고, 2와 3을 큐에 넣습니다.
- 그 다음, 2에 연결된 4와 5를 차례대로 방문하고, 2를 큐에서 반환 해 주고, 4와 5를 큐에 넣습니다.
- 그 다음, 3에 연결된 6과 7을 방문하고, 3을 큐에서 반환 해 주고, 6과 7을 넣습니다.
- 그 다음, 4에 연결된 5를 방문해야하지만, 이미 방문했으므로 큐에는 넣어주지 않고 4를 반환 해 줍니다.
- 그 다음, 5역시 큐에 넣지않고 반환 해 줍니다.
- 그 다음, 6에 연결된 7을 방문해야하지만 , 이미 방문했으므로 큐에 넣어주지않고 6을 반환 해 줍니다.
- 그 다음 7역시 큐에 넣지않고 반환 해 줍니다.
이제 코드로 보여드리겠습니다.
void BFS(int **map,Queue *queue,List * list,int *visit,int start) {
visit[start] = 1;
enqueue(list,index++,start);
printQueue(list);
while(list->count != 0) {
start = frontQueue(list);
deleteQueue(list);
for(int i = 1; i<vertex; i++) {
if(map[start][i] == 1 && visit[i] == 0) {
visit[i] = 1;
enqueue(list,index++,i);
printf("%d ",i);
}
}
}
}BFS 부분 코드입니다.
앞서 말씀드린 과정을 그대로 수행하는것을 볼 수 있습니다.
다음은 메인 코드를 보여드리겠습니다.
구조체
typedef struct Queue {
int data;
struct Queue* next;
struct Queue* prev;
}Queue;
typedef struct List {
struct Queue* tail;
int count;
}List;메인
int main() {
List *list = init();
Queue *queue;
int number;
int data1,data2;
int start;
printf("input link data count : ");
scanf("%d",&number);
printf("\n");
int **map = (int **)malloc(sizeof(int *) * number);
for(int i =0; i<=number; i++) {
map[i] = (int *)malloc(sizeof(int) * number);
}
int *visit = (int *)malloc(sizeof(int) * number);
for(int i =0; i<number; i++) {
printf("input data1, data2 : ");
scanf("%d %d",&data1,&data2);
map[data1][data2] = map[data2][data1] = 1;
visit[i] = 0;
vertex++;
}
printf("input start : ");
scanf("%d",&start);
printf("\n");
BFS(map,queue,list,visit,start);
for(int i =0; i<=number; i++) {
free(map[i]);
}
free(map);
free(visit);
return 0;
}list를 포인터형으로 List를 가리켜주고 , init() 이라는 포인터형 함수를 통해 list를 반환 하는 모습입니다. init은 다음과 같습니다.
List *init() {
List *list = (List *)malloc(sizeof(List));
if(list == NULL) printf("err\n");
else {
list->tail = NULL;
list->count = 0;
}
return list;
}map은 각 노드간의 연결을 하기위한 2차원 배열이며, 동적할당을 하였습니다.
visit 배열도 방문을 체크하기위한 배열로, 동적할당을 하였습니다.
vertex 는 간선의 갯수 입니다.
BFS 의 함수호출을 통해 너비우선탐색을 수행 합니다.
마지막으로 모든 소스코드를 보여드리며 마무리 해 보도록 하겠습니다.
#include <stdio.h>
#include <stdlib.h>
int vertex = 0;
int index = 0;
typedef struct Queue {
int data;
struct Queue* next;
struct Queue* prev;
}Queue;
typedef struct List {
struct Queue* tail;
int count;
}List;
List *init() {
List *list = (List *)malloc(sizeof(List));
if(list == NULL) printf("err\n");
else {
list->tail = NULL;
list->count = 0;
}
return list;
}
void enqueue(List *list,int index, int data) {
Queue *newQueue = (Queue *)malloc(sizeof(Queue));
Queue *preQueue = list->tail;
newQueue->data = data;
if(list->count == 0) {
newQueue->next = newQueue;
newQueue->prev = newQueue;
list->tail = newQueue;
list->count++;
}
else {
newQueue->next = preQueue->next;
newQueue->prev = preQueue;
preQueue->next = newQueue;
newQueue->next->prev = newQueue;
if(list->count == index) {
list->tail = newQueue;
}
list->count++;
}
}
void deleteQueue(List *list) {
Queue *curQueue = list->tail;
Queue *preQueue = list->tail;
if(list->count == 0){
printf("err\n");
return;
}
else {
for(int i =0; i<list->count; i++) {
list->tail = list->tail->next;
}
curQueue = list->tail->next;
list->tail->next = curQueue->next;
curQueue->next->prev = list->tail;
free(curQueue);
list->count--;
index--;
}
}
int frontQueue(List *list) {
Queue *curQueue = list->tail;
return curQueue->next->data;
}
void printQueue(List *list) {
int i;
if(list->count == 0) {
printf("none\n");
return;
}
else {
printf("%d ",list->tail->next->data);
}
}
void printQ(List *list) {
int i;
Queue *curQueue;
if(list->count == 0) {
printf("none\n");
return;
}
else {
for(i = 0, curQueue = list->tail->next; i<list->count; i++,curQueue = curQueue->next) {
printf("%d ",curQueue->data);
}
}
}
void BFS(int **map,Queue *queue,List * list,int *visit,int start) {
visit[start] = 1;
enqueue(list,index++,start);
printQueue(list);
while(list->count != 0) {
start = frontQueue(list);
deleteQueue(list);
for(int i = 1; i<vertex; i++) {
if(map[start][i] == 1 && visit[i] == 0) {
visit[i] = 1;
enqueue(list,index++,i);
printf("%d ",i);
}
}
}
}
int main() {
List *list = init();
Queue *queue;
int number;
int data1,data2;
int start;
printf("input link data count : ");
scanf("%d",&number);
printf("\n");
int **map = (int **)malloc(sizeof(int *) * number);
for(int i =0; i<=number; i++) {
map[i] = (int *)malloc(sizeof(int) * number);
}
int *visit = (int *)malloc(sizeof(int) * number);
for(int i =0; i<number; i++) {
printf("input data1, data2 : ");
scanf("%d %d",&data1,&data2);
map[data1][data2] = map[data2][data1] = 1;
visit[i] = 0;
vertex++;
}
printf("input start : ");
scanf("%d",&start);
printf("\n");
BFS(map,queue,list,visit,start);
for(int i =0; i<=number; i++) {
free(map[i]);
}
free(map);
free(visit);
return 0;
}큐 의 경우 연결리스트로 구현하였습니다.
다음으로 결과를 보여드리겠습니다.
위에 제가 그렸던 부분이랑 똑같이 연결하여, 출력되는것 까지 확인 해 보았습니다.
BFS는 개인적으로 이론은 간단하였지만, 생각보다 코드구현이 어려웠던 것 같습니다. 그래서 제가 알고있는 지식이랑 여러 블로그나 사이트 또는 책을 찾아보면서 분석하고 직접 그려보고 해 보았습니다. 연결리스트에 조금 더 익숙해져야 할 필요가 있다고 생각이 들었고, 탐색 또한 연습을 많이 해 보아야겠다고 생각이 들었습니다.
C++ 공부하고있는 대학생입니다.