너비우선탐색 (BFS)

lsh950223·2020년 5월 18일
0

안녕하세요 c++ 공부하고있는 대학생입니다.
이번에는 bfs에 대하여 정리하고자 합니다.

BFS 란? root노드로부터 인접한 노드 먼저 탐색하는 방법

BFS를 구현하기에 앞서 알아두어야 할 사항이 몇가지 있습니다.

  1. 시작점으로부터 가까운 점 먼저 방문하고 멀리떨어진 점을 나중에 순회한다.
  1. 두 노드 사이간 최단경로 또는 찾고자하는 경로가 있을 때 BFS를 사용한다.
  2. 반드시 노드를 방문 할 시, 방문했다는 체크를 해야한다.
  3. 자료구조 중 큐를 써야한다.

이렇게 4가지로 나눌 수 있습니다.

예시로 보여드리겠습니다.

이렇게 노드간 연결이 되었다고 가정을 하고, (root 노드는 1입니다.)
과정을 설명드리자면,

  1. 먼저 1을 방문하고 방문에 대한 체크를 해 줍니다. 그리고 큐에 넣습니다.
  1. 그 다음 2와 3을 차례대로 방문하고, 1을 큐에서 반환 해 주고, 2와 3을 큐에 넣습니다.
  2. 그 다음, 2에 연결된 4와 5를 차례대로 방문하고, 2를 큐에서 반환 해 주고, 4와 5를 큐에 넣습니다.
  3. 그 다음, 3에 연결된 6과 7을 방문하고, 3을 큐에서 반환 해 주고, 6과 7을 넣습니다.
  4. 그 다음, 4에 연결된 5를 방문해야하지만, 이미 방문했으므로 큐에는 넣어주지 않고 4를 반환 해 줍니다.
  5. 그 다음, 5역시 큐에 넣지않고 반환 해 줍니다.
  6. 그 다음, 6에 연결된 7을 방문해야하지만 , 이미 방문했으므로 큐에 넣어주지않고 6을 반환 해 줍니다.
  7. 그 다음 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는 개인적으로 이론은 간단하였지만, 생각보다 코드구현이 어려웠던 것 같습니다. 그래서 제가 알고있는 지식이랑 여러 블로그나 사이트 또는 책을 찾아보면서 분석하고 직접 그려보고 해 보았습니다. 연결리스트에 조금 더 익숙해져야 할 필요가 있다고 생각이 들었고, 탐색 또한 연습을 많이 해 보아야겠다고 생각이 들었습니다.

profile
C++ 공부하고있는 대학생입니다.

0개의 댓글