DFS와 비슷한 그래프 탐색 알고리즘으로 BFS가 있다.
DFS가 깊이를 우선적으로 탐색하는데 반해서, BFS는 말그대로 너비를 우선으로 탐색을 한다.
BFS는 시간 복잡도가 O(V+E)가 된다.
들어오는 input 그래프의 모양에 따라서 DFS가 더 효율적인 탐색이 될 수도 있고, BFS가 더 효율적인 탐색이 될 수도 있다.
BFS의 구현을 위해서 FIFO Queue를 이용한다.
DFS에서 사용했던 input 그래프를 그대로 사용한다.
그래프의 모양은 똑같지만, 탐색 순서가 DFS와 다른 것을 확인할 수 있다.
BFS의 탐색 알고리즘은 다음과 같다.
- 시작 정점을 큐에 enqueue
- if (큐가 비어있지 않다면 ) do
- 큐의 맨 앞 정점과 연결된 모든 정점을 큐에 삽입하면서 방문표시
- if (더이상 넣을 정점이 없다면) do
- 큐의 front 노드를 dequeue
2~5 까지 loop를 돌면 된다.
코드는 다음과 같다.
#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define MAX_FILE_NAME 50
#define NIL -1
#define TRUE 1
#define FALSE 0
#define NON_VISIT 2
#define VISITED 3
typedef struct _LIST {
int vertex;
struct _LIST *next;
} LIST;
typedef struct _QUEUE_NODE {
int key;
struct _QUEUE_NODE *next;
} QUEUE_NODE;
typedef struct _QUEUE {
struct _QUEUE_NODE *front;
struct _QUEUE_NODE *rear;
} QUEUE;
LIST *list_create(LIST *p, int eg_num);
void list_initialize(LIST *list, int numberOfVertices);
QUEUE_NODE *queue_create(int data);
void queue_initialize(QUEUE *q);
void queue_enqueue(QUEUE *q, int data);
int queue_dequeue(QUEUE *q);
int queue_isEmpty(QUEUE *q);
int queue_getValue(QUEUE *q);
void bfs(QUEUE *q, LIST *list, int numberOfVertices, int *path, int *visited);
void printArray(int numberOfVertices, int *path);
void printPath(int *path, int dst);
int main() {
FILE *fp_in;
LIST *list;
QUEUE *queue;
char input[MAX_FILE_NAME];
int numberOfVertices, numberOfEdges;
int i, x, y;
int *path, *visited;
printf("Enter the FILE Name or Path => ");
gets(input);
fp_in = fopen(input, "r");
if (fp_in == NULL) {
fprintf(stderr, "FILE <%s> open error.\n", input);
return -1;
}
fscanf(fp_in, "%d %d", &numberOfVertices, &numberOfEdges);
list = (LIST *) malloc(sizeof(LIST) * (numberOfVertices + 1));
if (list == NULL) {
fprintf(stderr, "Memory allocation error: *list\n");
return -1;
}
list_initialize(list, numberOfVertices);
for (i = 0; i < numberOfEdges; i++) {
fscanf(fp_in, "%d %d", &x, &y);
list_create(&list[x], y);
}
path = (int *) malloc(sizeof(int) * (numberOfVertices + 1));
if (path == NULL) {
fprintf(stderr, "Memory allocation error: *d\n");
return -1;
}
visited = (int *) malloc(sizeof(int) * (numberOfVertices + 1));
if (visited == NULL) {
fprintf(stderr, "Memory allocation error: *visited\n");
return -1;
}
queue = (QUEUE *) malloc(sizeof(QUEUE));
if (queue == NULL) {
fprintf(stderr, "Memory allocation error: *queue\n");
return -1;
}
bfs(queue, list, numberOfVertices, path, visited);
printArray(numberOfVertices, path);
printPath(path, 4);
printf("\n");
fclose(fp_in);
free(list);
free(queue);
free(path);
free(visited);
return 0;
}
LIST *list_create(LIST *p, int v) {
LIST *tmp, *pointer;
pointer = p;
tmp = (LIST *) malloc(sizeof(LIST));
if (tmp == NULL) {
fprintf(stderr, "Memory allocation error: list_create()\n");
return NULL;
}
tmp->next = NULL;
tmp->vertex = v;
while (TRUE) {
if (pointer->next == NULL) {
pointer->next = tmp;
break;
} else {
pointer = pointer->next;
}
}
return tmp;
}
void list_initialize(LIST *list, int numberOfVertices) {
int i;
for (i = 0; i <= numberOfVertices; i++) {
list[i].next = NULL;
list[i].vertex = -1;
}
}
QUEUE_NODE *queue_create(int data) {
QUEUE_NODE *tmp;
tmp = (QUEUE_NODE *) malloc(sizeof(QUEUE_NODE));
if (tmp == NULL) {
fprintf(stderr, "Memory allocation error: queue_create()\n");
return NULL;
}
tmp->key = data;
tmp->next = NULL;
return tmp;
}
void queue_initialize(QUEUE *q) {
q->rear = NULL;
q->front = NULL;
}
void queue_enqueue(QUEUE *q, int data) {
QUEUE_NODE *new_node;
new_node = queue_create(data);
if (queue_isEmpty(q) == TRUE) {
q->front = new_node;
q->rear = new_node;
} else {
q->rear->next = new_node;
q->rear = new_node;
}
}
int queue_dequeue(QUEUE *q) {
QUEUE_NODE *tmp, *remove;
int value;
if (queue_isEmpty(q) == TRUE) {
return -1;
}
remove = q->front;
tmp = q->front->next;
value = q->front->key;
q->front = tmp;
free(remove);
return value;
}
int queue_isEmpty(QUEUE *q) {
if (q->front == NULL) {
return TRUE;
} else {
return FALSE;
}
}
int queue_getValue(QUEUE *q) {
return q->front->key;;
}
void bfs(QUEUE *q, LIST *list, int numberOfVertices, int *path, int *visited) {
int i, u;
LIST *pointer;
for (i = 0; i <= numberOfVertices; i++) {
visited[i] = NON_VISIT;
path[i] = NIL;
}
queue_initialize(q);
queue_enqueue(q, 1);
visited[1] = VISITED;
while (queue_isEmpty(q) != TRUE) {
u = queue_getValue(q);
pointer = &list[u];
if (pointer->vertex == -1) {
pointer = pointer->next;
}
while (pointer != NULL) {
if (visited[pointer->vertex] == NON_VISIT) {
visited[pointer->vertex] = VISITED;
path[pointer->vertex] = u;
queue_enqueue(q, pointer->vertex);
}
pointer = pointer->next;
}
queue_dequeue(q);
}
}
void printArray(int numberOfVertices, int *path) {
int i;
printf("\n=====================================================\n");
printf("Index : ");
for (i = 1; i <= numberOfVertices; i++) {
printf("%3d ", i);
}
printf("\nP(bfs) : ");
for (i = 1; i <= numberOfVertices; i++) {
printf("%3d ", path[i]);
}
printf("\n=====================================================\n");
}
void printPath(int *path, int dst) {
if (path[dst] == -1) {
printf("%d ", dst);
return;
}
printPath(path, path[dst]);
printf("%d ", dst);
}
코드에서는, 시작 정점을 1로 가정하고 진행하였다.
위 코드를 실행하면 다음과 같은 결과를 얻게 된다.
