BFS-넓이 우선 탐색

BFS(Breadth First Search)는 기본적인 그래프 탐색 알고리즘이다.

 

한 지정 노드에서 출발하고, 먼저, 가장 근접한 노드들부터 방문합니다.

그 때, 그 중에서 가장 근접한 노드를 방문합니다.(->DFS와 차이점)

그 후, 방문하지 않은 노드가 없을 때 까지 노드를 방문합니다.

Kahn's Algorithm, Dijkstra's shortest path 와 같은 알고리즘이 이 BFS알고리즘을 기반으로 합니다.

 

트리와 마찬가지로 지정 노드에서 시작하는데, 이 때 문제점은 BFS는 지났던 노드를 다시 지나는 단점이 존재합니다.

 

 

BFS 작동 방식

0123456

1. 처음의 큐와 방문한 배열은 비어있습니다.

2.0을 큐에 넣고(push) 방문했음을 표기합니다.

3.큐의 앞부분(front)에서 앞서 넣은(push)를 제거하고 방문하지 않은 노드번호를 배열에 넣습니다(push).

4.3번과 같은 방식으로 큐의 front인 '1'을 제거하고 방문하지 않은 노드번호를 배열에 넣습니다(push).

5-7. 3번과 같은 방식으로 '2','3','4'를 제거한 후 같은 과정을 반복합니다.

 

<C로 위 사진의  알고리즘 구현>

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //논리자료형(True or False)

void bfs(int adj[100][100], int V, int s)
{
    //BFS의 Queue를 생성
    int q[100],front=0,rear=0; //배열의 공간, front와 rear의 초기값 설정
    bool visited[100]={false}; //stdbool.h 를 사용한 이유
    //노드를 방문했음을 표기하고, 큐에 push한다.
    visited[s]=true;
    q[rear++]=s;

    while(front<rear) //front가 rear과 같거나 커질때까지 반복
    {
        int curr=q[front++]; //정점을 pop
        printf("%d ",curr);

        //pop된 노드에 근접한 노드들을 불러오고
        //인접한 노드들 중 방문하지 않은 노드들을 방문
        for(int i=0; i<V; i++)
        {
            if(adj[curr][i]==1 && !visited[i])
            {
                visited[i]=true;
                q[rear++]=i;
            }
        }
    }
    printf("\n"); //"%" 출력 오류 제거
}

//표에 가장자리를 추가하는 함수
void addEdge(int adj[100][100],int u, int v)
{
    adj[u][v]=1;
    adj[v][u]=1; //간접적이지 않은 표
}

int main()
{
    int V=5; //그래프 내의 정점의 개수
    int adj[100][100]={0}; //붙어있는 행렬을 표현

    //가장자리 추가
    addEdge(adj,0,1);
    addEdge(adj,0,2);
    addEdge(adj,1,3);
    addEdge(adj,1,4);
    addEdge(adj,2,4);

    printf("0으로부터 BFS의 시작 위치 : \n");
    bfs(adj,V,0);

    return 0;
}

아래 사이트에 구현돼있는 알고리즘을 한국어로 해석하며 재개시함을 알립니다.

 

References

geekforgeeks

wikipia