[알고리즘] 너비 우선 탐색 - BFS (Breadth-First Search)

BFS : Breadth-First Search

너비 우선 탐색(Depth First Search) 에 대해서 알아보겠습니다.

 

너비 우선 검색시 방문 순서

위 그래프와 노드 번호는 너비 우선 검색을 Root 로 부터 시작하는 경우의 방문 순서를 보여주고 있습니다. 

각 노드에서 다음 단계(하위)의 노드로 이동하기 전에 노드의 모든 이웃을 방문하여 그래프를 탐색합니다.(Level-order)

방문하는 도중에 만나는 새로운 Node 가 있더라도 먼저 확인한 모든 이웃 Node를 먼저 방문하기 위해서는 선입선출(FIFO) 처리가 필요하게 되고, 이것은 BFS 는 Queue 와 같은 FIFO 를 처리할 수 있는 자료 구조를 사용하게 됨을 의미합니다.

 

Implementation

위에서 언급했듯이 BFS 에서는 Queue 를 사용하게 됩니다.

 

Backtracking 구현시 BFS 와 DFS 의 기본 구조는 유사합니다.

1. 각 노드를 어떻게 방문할 것인가의 관점에서 하위 노드의 정보를 대기열에 넣어주고 모든 곳을 방문합니다.
2. 추가 검색할 노드를 어떻게 관리하느냐에 따라서 순회 방식이 달라지게 되며, 대기열을 Queue 를 통해 관리하는 경우(BFS) 와 Stack (또는 재귀) 를 통해 관리하는 경우(DFS) 로 나뉘게 됩니다.
3. 각 노드를 방문한 다음 visit[ ] 과 같은 방문 처리를 해주어 다시 방문하지 않도록 해야 합니다.
4. 재귀함수를 사용할 경우에는 반드시 빠져나오는 구문을 만들어두어야 합니다.

 

그래프의 대기열 및 인접 행렬 표현을 사용하여 C로 구현된 폭 우선 검색 (BFS) 알고리즘의 예를 추가합니다.
이 코드에서, 그래프는 2D Array 사용하여 표현되고, addEdge 함수는 그래프에 간선을 추가하는 데 사용됩니다.

 

BFS 알고리즘은 큐를 사용하여 너비 우선 방식으로 정점을 방문합니다.
시작 정점으로 대기열을 초기화하고 방문한 것으로 표시하며 대기열이 비어 있을 때까지 프로세스를 계속합니다. 대기열에서 대기 중인 각 정점에 대해 아직 방문하지 않은 이웃 정점을 방문하여 대기하고 방문한 것으로 표시합니다.

#include <stdio.h>

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int queue[MAX_VERTICES];
int front = -1, rear = -1;

void initializeGraph() {
    int i, j;
    for (i = 0; i < MAX_VERTICES; i++) {
        visited[i] = 0;
        for (j = 0; j < MAX_VERTICES; j++) {
            graph[i][j] = 0;
        }
    }
}

void addEdge(int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1;
}

void enqueue(int vertex) {
    if (rear == MAX_VERTICES - 1) {
        printf("Queue is full\n");
        return;
    }
    if (front == -1) {
        front = 0;
    }
    rear++;
    queue[rear] = vertex;
}

int dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue is empty\n");
        return -1;
    }
    int vertex = queue[front];
    front++;
    return vertex;
}

void BFS(int startVertex, int numVertices) {
    printf("BFS traversal: ");
    printf("%d ", startVertex);
    visited[startVertex] = 1;
    enqueue(startVertex);

    while (front != -1) {
        int currentVertex = dequeue();

        int i;
        for (i = 0; i < numVertices; i++) {
            if (graph[currentVertex][i] && !visited[i]) {
                printf("%d ", i);
                visited[i] = 1;
                enqueue(i);
            }
        }
    }
    printf("\n");
}

int main() {
    int numVertices, numEdges;
    printf("Enter the number of vertices: ");
    scanf("%d", &numVertices);
    printf("Enter the number of edges: ");
    scanf("%d", &numEdges);

    initializeGraph();

    int i, u, v;
    for (i = 0; i < numEdges; i++) {
        printf("Enter edge %d (u v): ", i + 1);
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }

    int startVertex;
    printf("Enter the starting vertex for BFS: ");
    scanf("%d", &startVertex);

    BFS(startVertex, numVertices);

    return 0;
}

 

지금까지 그래프 순회, Backtracking 에서 사용되는 너비 우선 탐색의 개념과 코드를 살펴보았습니다.

 

 

※ 더 좋은 알고리즘 설명을 위해 내용은 조금씩 업데이트 될 수 있습니다.