[Data Structure] BFS (너비 우선 탐색)

BFS

- 너비 우선 탐색

- 원형큐로 구현

 

- 인접 행렬 : O(n²) (정점 n개)

- 인접 리스트 : O(n+e) (정점 n개, 간선 e개)

 

• 시작 정점으로부터 거리가 d인 정점들을 모두 방문 (d=1)
• 그 다음에 거리가 d+1인 정점들을 모두 방문
• d+2 / d+3,.... 정점들을 차례대로 방문

1. 거리가 0인 시작 정점(v)을 방문
2. v로부터 거리가 1인 정점 모두 방문
3. v로부터 거리가 2인 정점 모두 방문
4. 마지막 정점 방문할 때 까지.,....

 

 

인접 행렬로 구현한 BFS

Queue : bfs_mat_queue(graph* g, int v)

1. 큐 생성
2. v 방문완료 표시
3. v를 큐에 enqueue
4. 큐에서 dequeue (정점 v dequeue) -- (1)
5. dequeue된 정점 v의 인접 정점(w)들을 방문표시 하고, 큐에 enqueue -- (2)
   • enqueue 조건 : matrix[v][w] == 1 && visited[w] == FALSE
6. queue가 empty될 때 까지 (1), (2) 반복

void bfs_mat_queue(graph* g, int v) {
	queue* q;
	q = createQ(); init_queue(q);

	int w; // v의 인접 정점
	visited[v] = TRUE;
	enqueue(q, v);
	while (!is_empty(q)) {
		v = dequeue(q);
		printf("정점 %d -> ", v);
		for (w = 0; w < g->n; w++) {
			if (g->matrix[v][w] == 1 && visited[w] == FALSE) {
				enqueue(q, w);
				visited[w] = 1;
			}
		}
	}
}

 

 

인접 리스트로 구현한 BFS

Queue : bfs_list_queue(graph* g, int v)

1. 큐 생성
2. v 방문완료 표시
3. v를 큐에 enqueue 
4. 큐에서 dequeue (정점 v dequeue) -- (1)
5. dequeue된 정점 list[v]의 인접 graphnode의 정점(w->vertex)들을 방문표시 하고, 큐에 enqueue -- (2)
   • enqueue 조건 : visited[w] == FALSE
6. queue가 empty될 때 까지 (1), (2) 반복

void bfs_list_queue(graph* g, int v) {
	queue* q;
	q = createQ(); init_queue(q);

	visited[v] = TRUE;
	enqueue(q, v);
	graphnode* w;
	while (!is_empty(q)) {
		v = dequeue(q);
		printf("정점 %d -> ", v);
		for (w = g->list[v]; w; w = w->link) {
			if (visited[w->vertex] == FALSE) {
				visited[w->vertex] = TRUE;
				enqueue(q, w->vertex);
			}
		}
	}
}