[알고리즘] 너비 우선탐색(BFS)

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

 

너비 우선탐색(Breadth First Search)

 

BFS

 

1. 시작 노드를 큐에 넣는다.
2. Deque로 가져온 노드를 방문한 노드를 체크하는 v[]배열에 체크한다.
3. 인접한 노드 중 방문하지 않은 노드를 큐에 넣어준다.
4. 2~3번을 반복해준다.

 

---

 

소스코드

#define __main

#ifdef __main

#include <stdio.h>

#define MAX 128

typedef struct __Que {
	int* que; // 큐

	int max; // 큐의 최대입력 개수
	int num; // 현재 큐에있는 데이터 개수
	int front; // Deque할 위치
	int rear; // Enque할 위치
} Que;

int v[MAX] = { 0 };
int xy[MAX][MAX] = { 0 };

void Init(Que* q, int max) {
	q->que = malloc(sizeof(int) * max);

	q->max = max;
	q->front = q->rear = q->num = 0;
}

int Enque(Que* q, int x) {
	if (q->num >= q->max) return -1; // 큐가 가득참

	q->num++;
	q->que[q->rear++] = x;

	q->rear %= q->max; // 0 -> 1 -> ... -> max -> 0 -> 1

	return 0;
}

int Deque(Que* q, int* x) {
	if (q->num <= 0) return -1; // 큐가 비어있음

	q->num--;
	*x = q->que[q->front++];

	q->front %= q->max; // 0 -> 1 -> ... -> max -> 0 -> 1

	return 0;
}

void BFS(Que* q, int n, int start) {
	int tmp = 0;

	v[start] = 1;
	Enque(q, start);

	while (Deque(q, &tmp) == 0) {
		printf("%d 번 노드 방문\n", tmp);
		for (int i = 0; i < n; i++) {
			if (xy[tmp][i] == 1 && v[i] == 0) {
				Enque(q, i);
				v[i] = 1;
			}
		}
	}
}

int main() {
	Que* q = malloc(sizeof(Que));

	int n, m, start, x, y;

	scanf("%d %d %d", &n, &m, &start);

	Init(q, n);

	for (int i = 0; i < m; i++) {
		scanf("%d %d", &x, &y);

		xy[x][y] = xy[y][x] = 1;
	}

	BFS(q, n, start);

	free(q->que);

	return 0;
}

/*

Test Input Data

10 9 0
0 1
0 2
0 3
3 4
3 6
4 8
6 7
7 9
5 9
*/

#endif