#9 DFS & BFS

그래프 탐색이란?

그래프의 한 정점으로 부터 출발해서 모든 정점을 1번씩 방문하여 그래프에 대한 정보를 얻는 것

정점 방문 순서에 따라 크게 두 방식으로 나뉨

깊이 우선 탐색(DFS) / 너비 우선 탐색 (BFS)

 

DFS(깊이 우선 탐색)

다음 분기(brunch)로 넘어가기 전에 현재 분기를 완전히 탐색하는 방법

트리의 전위(preorder)탐색이 그래프로 확장된 개념

재귀 함수 or 스택으로 구현

 

1) 정점 1개를 선택한다.

2) 현재 정점과 이웃한 정점 중 아직 방문하지 않은 정점 중 하나를 방문한다.

3) 더 이상 방문할 수 있는 정점이 없는 경우, 현재 정점의 이전 정점으로 돌아간다.

4) 모든 정점을 방문할 때까지 2~3을 반복한다.

왼쪽의 그래프를 dfs를 통한 순서를 오른쪽 dfs tree로 나타내었다.

dfs tree는 나중에 고급알고리즘에 활용할 수 있다.(ex ETT 등)

 

DFS 구현 (재귀함수)

bool visited[MAX];
vector<int>adj[MAX];
void dfs(int u) {
	visited[u] = true;
	for (auto nxt : adj[u]) {
		if (!visited[nxt])
		   dfs(nxt);
	}
}

 

BFS (너비 우선 탐색)

인접한 정점들을 먼저 탐색하는 방법

가까운 정점을 먼저, 먼 정점을 나중에

큐(Queue)로 구현

1) 정점 1개를 선택한다.

2) 현재 정점(u)과 이웃한 정점(v)중 방문하지 않은 정점을 모두 방문한다.

3) v중 가장 먼저 방문한 이웃한 정점으로 이동한다.

4) 모든 정점을 방문할 때까지 2~3을 반복한다.

 

BFS 구현

bool visited[MAX];
vector<int>adj[MAX];
int main() {
	queue<int>q;
	q.push(root);
	visited[root] = true;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : adj[u]) {
			if (!visited[v]) {
				visited[v] = true;
				q.push(v);
			}
		}
	}
}

 

DFS vs BFS

<공통점>

그래프의 모든 정점을 1번씩 방문할 수 있음

시간복잡도가 동일

인접행렬 : O(N^2)

인접 리스트 : O(N + E)

 

<차이점>

DFS :

재귀호출 또는 스택 사용

재귀 호출로 인한 시간 소모

지나온 경로를 알아야 할 때 주로 사용

 

BFS :

큐 사용

다음에 방문할 정점 저장으로 인해 메모리 소모

최단 거리를 구할 때 주로 사용

 

예시문제

백준 1012 (유기농 배추) c++