[알고리즘] 넓이 우선 탐색 (BFS)

오늘은 넓이 우선탐색에 대해 알아보겠습니다.

 

넓이 우선탐색은 거리를 기준으로 하는 탐색 방법이라 할 수 있습니다. 즉, 시작점으로부터 거리가 같은 노드를 먼저 탐색하는 방법입니다.

 

아래 그래프를 기준으로 설명하겠습니다.

거리가 동일할 때는 작은 숫자부터 탐색한다고 가정하면

시작점이 0일때 BFS 방식을 사용하면, 0->1->4->2->3 순서로 그래프를 탐색하게 됩니다.

0과 인접한 1과 4를 먼저 탐색하게 됩니다. 

0과 인접한 것은 이제 없기 때문에 1과 인접한 것 중 이전에 탐색하지 않았던 노드인 2와 3을 탐색하게 됩니다.

1과 인접한 것은 이제 없고 4와 인접한 것 중 이전에 탐색하지 않았던 노드는 없기 때문에 탐색을 종료합니다.

 

 

위의 그래프를 인접 행렬 방식으로 나타내면 다음과 같습니다.

 

탐색한 노드를 저장할 queue가 있고, 인접한 노드를 탐색할 기준 노드를 가리키는 first가 있습니다.

이미 탐색을 한 노드인지 아닌지 알 수 있는 visited 배열이 있고 처음에는 모두 0으로 초기화 되어있습니다.

탐색이 진행되는 순서를 아래 그림으로 표현해 보았습니다.

 

 

 

 

 

 

 

 

 

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

int graph[5][5] = { {0,1,0,0,1}, {1,0,1,1,1}, {0,1,0,1,0},
						{0,1,1,0,1}, {1,1,0,1,0} };

void bfs(int start, int vertex) {
	int* queue = (int*)malloc(sizeof(int) * vertex);
	int* visited = (int*)malloc(sizeof(int) * vertex);
	memset(visited, 0, vertex * sizeof(int));
	int first = 0;
	queue[0] = start;
	visited[start] = 1;
	int idx = 1;

	while (idx < vertex) {
		for (int i = 0; i < vertex; i++) {
			if (graph[queue[first]][i] == 1) {
				if (visited[i] == 0) {
					queue[idx] = i;
					idx++;
					visited[i] = 1;
				}
				
			}
		}
		first++;
	}

	for (int i = 0; i < vertex; i++) {
		printf("%d ", queue[i]);
	}

	free(queue);
	free(visited);
}

int main() {
	bfs(0, 5);
	return 0;
}