BFS_너비우선탐색

너비우선 탐색 (BFS)

-      왜 너비우선 탐색인가?

-      깊이 우선탐색과의 차이점

Concept

인접한 노드를 차례로 모두 방문하는 것

Queue를 이용한다.

 

왜 너비우선 탐색인가?

- 탐색순서 A-(B-C-D)-(E-F)

- height가 낮은 순서대로 탐색한다.

깊이 우선탐색과의 차이점

너비우선탐색

- 최소신장트리, 최단경로

- 무한히 깉은 트리에 효과적

- 목표노드로 가는 경로가 모두 같은 weight일때 비효율적

깊이우선 탐색

- 사이클 탐지, 위상정렬

- 무한히 넓은 트리에 효과적

- 목표노드가 없는 경로에 계속 빠질 수 있다.

Queue를 사용하여 탐색한다.

#Queue

A

pop A

push B, C ,D

(pop A)

B

C

D

pop B

push E

(pop B)

C

D

E

pop C

push F

(pop C)

D

E

F

pop D ...

pop E ...

pop F ...

 

Code

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

vector<vector<int>> adj;//그래프의 인접리스트 표현

vector<int> bfs(int start){
	vector<bool> discovered(adj.size(), false);//정점의 방문 여부 기록
	queue<int> q;//방문할 정점의 목록
	
	
	vector<int> order;//bfs결과
	discovered[start] = true;// 방문을 했다고 해주고
	q.push(start);
	
	while(!q.empty()){// 안의 조건을 만족하면 반복
		int here = q.front();
		q.pop();//맨 앞의 큐를 하나꺼내고
		order.push_back(here);
		
		for(int i=0;i<adj[here].size();i++){//인접한 크기만큼
			int there = adj[here][i];//인접한 i 번째 정점
			if(!discovered[there]){//false 라면
				q.push(there);//q에 정점의 idx를 넣어주고
				discovered[there]=true;//방문했다고 표시
			}
		}
		
	
	}
	
	return order;
	
}

 

예제

-  유기농 배추_클릭