[C언어] BFS (Breadth First Search)

이번 포스팅은 인접 행렬과 visted을 통한 BFS Algorithm을 구현해본다.  BFS는 DFS와 함께 공부 되는것이 좋으니 아래 DFS도 참고하도록 한다. 아래 DFS에서는 인접행렬에 대한 내용도 다룬다. BFS와 내용이 중복되니 이번 포스팅에서는 생략한다.

http://soye0n.tistory.com/13?category=764669

Keywords

- Vertex = Edge : 정점, 꼭 (0,1,2,3,4,5,6,7)를 의미한다.
- 인접 행렬 : 그래프 이론에서, 인접행렬 (Adjacency Matrix)은 그래프에서 어느 꼭짓점(Vertex)들이 어느 변으로 연결되어 있는지를 나타내는 정사각형 행렬이다. 
- Visited : 어느 꼭짓점을(Vertex)방문 했는가에 대한 여부, flag같은 개념

이것만 기억하자!
 - 어떤 Vertex에서 인접해있는 Vertex를 모두 방문하자.

시나리오
Start Vertex는 0
1. 우선 Queue에 vertex 0을 넣어준다.
2. Queue에서 요소를 빼는데, 이때 요소는 Current Vertex 이다. (이 Current Vertex를 반복문으로 돌면서 위치를 바꿔가며 Queue에 넣을 것임)
3. Current Vertex에서 인접한 요소들을 Queue에 넣어준다. 단 이때 요소는 한번도 방문된적이 없는 요소여야 한다. (visited != true(1))
4. 더이상 Current Vertex에 인접한 요소가 없으면 Queue에서 요소 하나를 뺀다. (Dequeue)
5. 2번-4번 반복

BFS

45 void BFS(Graph* graph, int vertex){ 46 47 Queue* queue = createQueue(); 48 int i=0; 49 enQueue(queue, vertex); 50 printf("%d visited \n", vertex); 51 52 while(!isEmpty(queue)){ 53 vertex = deQueue(queue); 54 55 for(i=vertex; i<graph->numOfVertex; i++){ 56 if(!graph->visited[i] && graph->matrix[vertex][i] == 1){ 57 graph->visited[i] = 1; 58 enQueue(queue, i); 59 printf("%d visited \n", i); 60 } 61 } 62 } 63 }

line 49 : 첫번째 시작되는 Vertex를 queue에 넣어준다.
line 52 : queue가 비어있지 않는 동안 아래 작업들을 수행한다.
line 53 : queue가 비어있지 않으면 우선 하나씩 dequeue를 한다. 
line 55 : 현재 vertex부터 vertex의 수만큼 전수 조사하여 인접된 행렬과 방문된적이 한번도 없는 vertex를 찾는다.
line 56 : 아직 방문된적이 없고 인접행렬이면 해당 vertex를 방문할 것이기 때문에 visited flag를 1로 set해준다.
line 57 : 방문된 vertex는 queue에 넣어준다. 

결과 화면

전체 소스

필요한 소스 : include/queue.h , queue.c, bfs.c
$ gcc -I./include -o bfs bfs.c queue.c
queue.c 소스는 아래 URL를 참고 한다.

http://soye0n.tistory.com/12?category=764668

bfs.c

#include <stdio.h> #include <stdlib.h> #include <memory.h> #include <queue.h> typedef struct Graph{ int numOfVertex; int **matrix; int *visited; }Graph; Graph* makeGraph(int numOfVertex){ int i=0; Graph *graph = (Graph*)malloc(sizeof(Graph)*numOfVertex); graph->matrix = (int**)malloc(sizeof(int*)*numOfVertex); graph->visited = (int*)malloc(sizeof(int)*numOfVertex); graph->numOfVertex = numOfVertex; for(i=0; i<numOfVertex; i++){ graph->matrix[i] = (int*)malloc(sizeof(int)*numOfVertex); memset(graph->matrix[i], 0, sizeof(int)*numOfVertex); graph->visited[i] = 0; } return graph; } void addEdge(Graph* graph, int start, int end){ graph->matrix[start][end] = 1; graph->matrix[end][start] = 1; } void printGraph(Graph *graph) { int i, j; for (i = 0; i < graph->numOfVertex; i++) { printf("start %d ->", i); for (j = 0; j < graph->numOfVertex; j++) { printf("%d ", graph->matrix[i][j]); } printf("\n"); } } void BFS(Graph* graph, int vertex){ Queue* queue = createQueue(); int i=0; enQueue(queue, vertex); printf("%d visited \n", vertex); while(!isEmpty(queue)){ vertex = deQueue(queue); for(i=vertex; i<graph->numOfVertex; i++){ if(!graph->visited[i] && graph->matrix[vertex][i] == 1){ graph->visited[i] = 1; enQueue(queue, i); printf("%d visited \n", i); } } } } int main(void) { Graph *graph; graph = makeGraph(8); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 3); addEdge(graph, 1, 4); addEdge(graph, 3, 7); addEdge(graph, 4, 7); addEdge(graph, 2, 5); addEdge(graph, 2, 6); addEdge(graph, 6, 7); addEdge(graph, 5, 7); printGraph(graph); BFS(graph, 0); return 0; }

참고 문헌 : https://www.programiz.com/dsa/graph-bfs