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

1. 너비우선탐색

   - 큐를 이용하여 깊이가 같은 노드를 모두 방문하고 깊이를 증가시키며 탐색하는 알고리즘이다.

2. 동작원리

   1) 지정한 시작 노드에서부터 시작

   2) 자식 노드들을 큐에 저장한다

   3) 큐에 저장된 노드를 차례로 방문하면서 방문한 노드의 자식들을 큐에 저장

   4) 큐에 있는 요소를 방문하면서 2) 3)의 과정을 반복

   5) 모든 노드를 방문하면 탐색을 종료

   

3. 소스

1. #include<stdio.h>
2.  
3.  
4. int front = -1;
5. int rear;
6.  
7. void inqueue(int *,int);  // 큐에 데이터를 삽입하는 연산
8. int dequeue(int *);  // 큐에서 데이터를 빼는 연산
9. int queueempty(); // 큐가 비어있는지 검사
10.  
11. int matrix[6][6] = {{0,1,1,0,0,0},
12.                     {1,0,1,1,0,0},
13.                     {1,1,0,1,1,0},
14.                     {0,1,1,0,1,1},
15.                     {0,0,1,1,0,0},
16.                     {0,0,0,1,0,0}};
17. int visit[6];
18.  
19.  
20. int main(void)
21. {
22.     int a=0;
23.     int b=0;
24.     int now = 0;
25.  
26.     int queue[40] = {0,};
27.  
28.     visit[0] = 1; // 처음방문할 정점
29.  
30.     inqueue(queue,0);
31.     printf("%d ",now);
32.  
33.  
34.     while(queueempty())
35.     {
36.         now = dequeue(queue); // 큐의 원소를 빼내 인접 노드를 찾는다
37.  
38.         if(visit[now] == 0)  // 인접노드중 방문하지 않은 노드를 찾기위해 vist배열을 검사
39.         {
40.             printf("%d ",now);
41.             visit[now] = 1;
42.         }
43.  
44.         for(a=0;a<6;a++) // 현재 노드의 인접 노드를 큐에 저장하기 위한 for문
45.         {
46.             if(matrix[now][a] == 1 && visit[a] == 0)
47.                     inqueue(queue,a);
48.         }
49.        
50.     }
51.     return 0;
52. }
53.  
54. int queueempty()
55. {
56.     if(front == rear)
57.         return 0;
58.     else
59.         return 1;
60. }
61.  
62. void inqueue(int *queue, int data)
63. {
64.     if(rear == 40)
65.         printf("큐가 꽉찾습니다.\n");
66.     else
67.         (*(queue + (rear++))) = data;
68. }
69.  
70. int dequeue(int * queue)
71. {
72.     int data;
73.  
74.         data = (*(queue+(++front)));   
75.         return data;
76.    
77.  
78. }

4. 결과