[Algorithm] BFS 정리

1. BFS란?

- BFS 는 너비우선탐색을 말합니다.

- 루트 노드에서 시작하여 인접한 노드를 탐색하는 방법입니다.

 

 

 

Q. 너비우선 탐색을 하면 순서가 어떻게 될까요?

 

 A. 0 - 1 - 2 - 3 - 4 - 5 -6

 

 

 

 

 

 

 

1) 특징

- 두 노드사이의 최단 경로를 찾을 때, 임의의 경로를 찾을 때 사용

- 코드가 DFS보단 복잡하지만 속도는 더 빠르다

 

2) 알고리즘 구현 방법

 

 

BFS의 결과 :

1 - 2 - 6 - 3 - 4 -5

 

 

 

 

 

- 큐를 이용하여 구현함

void bfs(int st) {
	q.push(st);
	visited1[st] = 1;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		printf("%d ", now);
		for (int i = 0; i < adj[now].size(); i++) {
			int next = adj[now][i];
			if (!visited1[next]) {
				q.push(next);
				visited1[next] = 1;
			}	
		}
	}
}

- 과정

1. bfs에 1이 들어가면 큐에 1이 푸쉬됨.
2. visited배열에서 1은 방문함을 표시
3. 큐가 비어있지 않으므로 while문안에 들어감
4. 큐에 첫번째에 있는 노드(1)가 now가 되고
5. 1은 큐에서 삭제됨
6. 1의 인접노드의 개수만큼 for문 반복
7. next = 다음 방문할 노드
8. 만약에 방문하지 않은 노드라면 q에 푸쉬한다. 
9. 그리고 방문했다고 표시

.. 이하생략

 

---