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로 가정하고 진행하였다.
위 코드를 실행하면 다음과 같은 결과를 얻게 된다.