Breadth First Search (BFS)

DFS와 비슷한 그래프 탐색 알고리즘으로 BFS가 있다.
DFS가 깊이를 우선적으로 탐색하는데 반해서, BFS는 말그대로 너비를 우선으로 탐색을 한다.
BFS는 시간 복잡도가 O(V+E)가 된다.
들어오는 input 그래프의 모양에 따라서 DFS가 더 효율적인 탐색이 될 수도 있고, BFS가 더 효율적인 탐색이 될 수도 있다.

BFS의 구현을 위해서 FIFO Queue를 이용한다.
DFS에서 사용했던 input 그래프를 그대로 사용한다.
그래프의 모양은 똑같지만, 탐색 순서가 DFS와 다른 것을 확인할 수 있다.
BFS의 탐색 알고리즘은 다음과 같다.

  1. 시작 정점을 큐에 enqueue
  2. if (큐가 비어있지 않다면 ) do
  3. 큐의 맨 앞 정점과 연결된 모든 정점을 큐에 삽입하면서 방문표시
  4. if (더이상 넣을 정점이 없다면) do
  5. 큐의 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로 가정하고 진행하였다.
위 코드를 실행하면 다음과 같은 결과를 얻게 된다.

댓글 남기기