알고리즘) 그래프의 탐색 - DFS, BFS

# 그래프의 탐색의 목적 

임의의 정점에서 시작하여 연결되어 있는 모든 정점을 1번씩 방문하는 것

(1번 이상 방문하면 그것은 DFS, BFS가 아님)

 

DFS, BFS는 어떤 순서로 정점을 방문하는 것인가에 차이를 갖는다.

 

# DFS (깊이 우선 탐색)

한 정점에서 시작하여 최대한 깊게 탐색(새로운 연결된 정점이 없을 때까지)하고

더 이상 깊게 탐색할 정점이 없으면 탐색해온 경로를 되돌아오면서 다시 탐색한다.

(새로운 정점 : 방문한 적이 없는 정점)

(사람 1명이 탐색을 하는 것이라고 비유할 수 있다.)

 

 

DFS 탐색 순서

# BFS (너비 우선 탐색)

탐색을 시작한 정점부터 각 정점에서 방문 가능한(연결되어 있는) 모든 새로운 정점들을 1번에 확인하는 방식으로 탐색한다.

(사람이 연결된 정점의 수만큼 복제되면서 탐색하는 것이라고 비유할 수 있다.)

 

# DFS 구현

- Stack 사용 

더 이상 갈 수 있는 정점이 없을 때, 어디로 돌아가야 하는지 알려주는 역할을 한다.

탐색을 수행해오는 경로를 저장하는 기능을 Stack을 통해 구현한다고 할 수 있다.

cf) Stack이 비면, 모든 정점을 방문하고 탐색을 종료하는 시점이 된다.

- 배열 사용

각 정점에 대한 방문 여부를 저장하는 배열로 사용한다.

 

Stack의 자료 구조와 같은 구조로 작동하는 재귀함수의 특징을 이용하여

DFS는 재귀함수로 구현할 수 있다.

 

아래는 인접 행렬로 표현된 그래프에 대한 DFS를 재귀함수로 구현한 코드이다.

void dfs(int x) {
	check[x] = true; // 방문한 정점은 방문했다고 처리
	for (int i=1; i<=n; i++) { // 각 정점마다 모든 정점에 대해서 확인
		if (a[x][i] == 1 && check[i] == false) { // 두 정점 사이의 간선이 있고, 방문한 적 없는 정점이면
			dfs(i); // 탐색 수행
		}
	}
}

아래는 인접 리스트로 표현된 그래프에 대한 DFS 코드이다.

void dfs(int x) {
	check[x] = true;
	for(int i=0;i<a[x].size();i++) { // 각 정점마다 연결되어 있는 차수만큼 검사
		int y = a[x][i];
		if (check[y] == false) { // 방문한 적 없는 정점이라면
			dfs(y);
		}
	}
}

인접 행렬에 대한 DFS의 시간복잡도는 O(V^2)이고

(모든 정점들을 방문(O(V))하며, 각 방문하는 정점마다 모든 정점에 대한 조건 판별을 수행(*O(V))하기 때문)

인접 리스트에 대한 DFS의 시간복잡도는 O(V+E)이다

(모든 정점들을 방문하며(O(V)), 각 정점들의 차수만큼 조건 판별을 수행하는데, 각 정점들의 차수의 합은 곧 그래프의 간선의 개수와 같기 때문에 O(E)만큼의 시간이 추가로 걸린다고 할 수 있다.

이 때, 항상 V<=E가 성립하기 때문에 인접 리스트에 대한 DFS의 시간복잡도는 O(E)라고 할 수도 있다.

 

# BFS 구현

- Queue 사용

내가 방문해야할 정점들을 Queue를 사용해서 관리한다.

1. 특정 정점에서 방문할 수 있는 모든 정점들을 Queue에 넣는다.

   Queue에 들어가는 정점들은 방문한 것으로 처리되며, Queue에 들어가는 순간 처리된다.

   (Queue에서 나갈떄 처리되면 정점을 중복 방문할 가능성이 생기기 때문)

2. 방문하고 나간 정점은 Queue에서 pop() 해준다. 

3. Queue가 비면, 모든 정점들을 탐색하고 종료되는 시점이 된다.

- 배열 사용 

DFS와 같이 정점의 방문 여부를 기록하기 위한 배열이 필요하다.

 

BFS 알고리즘은 모든 간선들의 가중치가 1일때, 정점 간의 최단 거리를 구할 수 있다는 점에서 중요하다.

 

사실상 알고리즘이 수행하는 기능은 DFS와 같기 때문에 시간복잡도는 DFS와 동일하다.

(인접 행렬 : O(V^2), 인접 리스트 : O(E))

 

아래 코드는 인접 행렬로 구현된 그래프 대해 BFS를 구현한 코드이다.

queue<int> q;
check[1] = true; q.push(1);
while (!q.empty()) {
	int x = q.front(); q.pop();
	for (int i=1; i<=n; i++) {
		if (a[x][i] == 1 && check[i] == false) {
			check[i] = true;
			q.push(i);
		}
	}
}

 

아래 코드는 인접 리스트로 구현된 그래프에 대해 BFS를 구현한 코드이다.

queue<int> q;
check[1] = true; 
q.push(1);
while (!q.empty()) {
	int x = q.front(); q.pop();
	for (int i=0;i<a[x].size();i++) {
		int y = a[x][i];
		if (check[y] == false) {
			check[y] = true; q.push(y);
		}
	}
}