너비우선탐색(BFS : Breadth First Search)

너비우선탐색(BFS : Breadth First Search)

- 자노드를 탐색하기 전 같은 위치의 노드를 먼저 탐색하는 방식이다.

- BFS의 시간 복잡도 및 공간 복잡도는 O(nⁿ)이다. ( 주어진 모든 노드를 저장하기 때문 )

- 무한히 깊은 트리에 효과적이다.

[ Fig. 1] BFS 탐색 순서

 

1. 동작 원리

(1) 시작 노드를 큐(Queue)에 삽입한다.

(2) 큐가 비어있다면 수행을 중단한다.

(3) 큐에서 노드를 꺼낸다.

(4) 꺼내온 노드를 기준으로 인접한 정점 중 탐색하지 않은 노드를 탐색한다.

(5) 탐색한 노드를 순차적으로 큐에 삽입한다.

(6) (2 - 5) 과정을 반복한다.

2. 함수 구현

#include <stdio.h> #define MAX 6 #define VISITED 2 #define ADJACENCY 1 typedef struct queue{  int data[MAX];  int front;  int rear; }QUEUE; int G[MAX][MAX] = // init adjacency matrix {{0,1,1,0,0,0}, {1,0,0,1,1,0}, {1,0,0,0,0,1}, {0,1,0,0,0,0}, {0,1,0,0,0,0}, {0,0,0,0,1,0}}; int visit[MAX]; // to check whether visited or not char vc[MAX+1] = {"ABCDEF"}; // allocate alphabets to each vertical. QUEUE q; // this variable is used as the queue. void bfs( int); void enqueue( int); int dequeue( void); int queue_empty( void); int main( void) {  bfs( 0); // call function with a starting vertical. } /*  store a data in the queue */ void enqueue( int v) {  q.data[q.front++] = v; } /*  pick the data that stored recently up from the queue */ int dequeue( void) {  return q.data[q.rear++]; } /*  check whether the queue is empty or not. */ int queue_empty( void) {  return q.front == q.rear; } /*  Breadth First Search function  - this function uses recursion to search root. */ void bfs( int v) {  int i;  enqueue( v); // insert a data into the queue.  // examine whether the queue is empty or not  while( !queue_empty())  {   v = dequeue(); // pick up the vertical from the queue.   visit[v] = VISITED; // mark this vertical as VISITED.   for( i = 0 ; i < MAX ; i ++)   {    // find a adjacency vertical that have never visited before.    if( !visit[i] && G[v][i] == ADJACENCY)    {       // insert the vertical that has found into the queue.     enqueue(i);     printf("%c에서 %c로 이동\n", vc[v], vc[i]);    }   }  } }

3. 실행 결과

Fig. 1의 그래프를 기준으로 구현한 결과, 이론과 일치하는 순서대로 출력되었다.