그래프의 탐색(DFS, BFS)

그래프에 정보를 저장했으면, 정보를 사용하기 위해서는 그래프에 어떤 정보가 어떻게 저장되어 있는지 파악해야 할 것이다.

그래프를 탐색하면 그래프를 탐색하는 과정에서 간선이 어떠한 방식으로 연결되어있는지, 탐색 순서는 어떻게 되었는지 등을 통해서 그래프의 전체적인 구조를 파악할 수 있다.

즉, 그래프 탐색의 목적은 임의의 정점에서 시작하여 연결되어있는 모든 정점을 한 번씩 방문하면서 그래프의 구조를 파악하는 것에 있다.

그렇다면 그래프는 어떠한 방법으로 탐색할 수 있을까?

 

그래프를 탐색하는 방법은 대표적으로 DFS와 BFS의 두 가지가 있다.

 

1. 깊이 우선 탐색(Depth-First Search, DFS)

DFS는 임의의 정점에서 시작하여 방문할 수 있는 정점 중 하나를 방문하고, 방문한 정점에서 방문할 수 있는 정점 중 하나를 방문하고를 이어가다가 더 이상 갈 곳이 없는 정점에 도달한다면 이전 정점으로 돌아가서 방문할 정점이 있는지를 판단하는 탐색 방법이다.

한 사람이 정점을 이동하며 그래프를 탐색한다고 생각하면 쉽게 이해할 수 있다.

정점을 타고 들어가며 항상 자신이 탐색중인 정점부터 길이 있는지를 판단하기 때문에, 스택으로 구현하기 적합하다.

DFS는 스택과 재귀를 이용해서 각각 구현할 수 있는데, 둘 다 방법을 살펴보도록 하겠다.

 

탐색을 구현할 때에는 각 정점 당 한 번씩만 방문해줘야 하기 때문에 해당 정점에 방문했는지를 판단할 boolean타입의 배열을 사용한다.

구현은 모두 인접 리스트를 이용하여 해주었다.

 

● DFS의 구현

아래의 그래프에서 1정점부터 DFS로 탐색을 진행하는 경우를 알아보도록 하자.

방문하는 정점을 우선 스택에 담아주고, 해당 정점과 연결된 모든 경로를 탐색했을 때 이전의 정점으로 돌아가면서 스택에서 제거해준다.

스택이 완전히 비어있을때까지 탐색하면 DFS가 완료된다.

 

*DFS를 할 때는 연결된 어떤 정점부터 방문하던지 상관 없지만, 일관성을 위해서 숫자가 가장 작은 정점부터 방문한다는 것을 전제로 탐색하였다.

정점 방문 순서는 1-2-4-3-5이다.

<스택을 이용하여 구현>

// 방문여부를 저장할 배열
boolean[] check = new boolean[n + 1];
// DFS 탐색을 위해 Stack을 이용한다.
Stack<Integer> stack = new Stack<Integer>();
// 임의의 정점 1부터 탐색을 시작하기 위해 스택에 1을 넣어주고 방문 배열을 true로 변경해준다.
check[1] = true;
stack.push(1);

// 스택이 완전히 빌때까지 탐색한다.
while (!stack.isEmpty()) {
	// 현재 있는 정점(=스택의 peek값)의 인접 리스트를 탐색하며 방문할 수 있는 정점이 있는지 판단한다.
	int x = stack.peek();
	for (int j = 0; j <= adj[x].size(); j++) {
	if (j == adj[x].size()) {
		// 현재 정점에서 더 이상 방문할 정점이 없다면 pop을 해주어 이전 정점으로 이동한다.
		stack.pop();
		break;
	}

	int v = adj[x].get(j);
	// 아직 방문하지 않은 정점이 있다면
	if (!check[v]) {
		// 그 정점으로 이동
		stack.push(v);
		check[v] = true;
		break;
	}
}

<재귀를 이용하여 구현>

재귀를 쓰면 스택을 쓰지 않아도 되고 훨씬 간편하게 코드를 짤 수 있어서 재귀로 구현하는 것을 선호한다.

private static void dfs(int x) {
	// 정점에 방문했음을 표시
	check[x] = true;
	for(int i = 0; i < adj[x].size(); i++) {
		int v = adj[x].get(i);
		if(!check[v])
			dfs(v);
	}
}

 

 

2. 너비 우선 탐색(Breadth First Search, BFS)

한 명의 사람이 정점을 탐색하는 DFS와는 반대로, BFS는 정점이 정점을 탐색하는 느낌이라고 볼 수 있다.

BFS에서는 한 정점에서 갈 수 있는 모든 정점을 우선적으로 방문한다. 그 다음에, 다음 정점으로 넘어가서 다음 정점에서 탐색할 수 있는 모든 정점을 방문한다. 만약 그 정점에서 더 이상 방문할 수 있는 곳이 없다면 바로 다음 정점으로 넘어가서 탐색을 이어나가는 방식이다.

 

● BFS의 구현

BFS는 큐를 이용해서 구현할 수 있다.

아래의 그래프에서 1정점부터 BFS로 탐색을 진행하는 경우를 알아보도록 하자.

첫 번째 정점을 우선 큐에 담아주고, 해당 정점과 연결된 모든 정점을 큐에 담아준다.

연결된 정점을 큐에 모두 담았으면, 원래의 정점을 poll해준다.

그러면 큐의 peek값을 읽으면 현재의 정점을 알 수 있게 되는데, 현재의 정점에서도 check배열을 통해 방문한 적이 없는 정점을 판단하여 방문할 수 있는 정점을 모두 큐에 담아준다. 그 후 원래 정점을 poll한다.

큐가 완전히 비어있을때까지 탐색하면 연결된 모든 정점을 탐색할 수 있다.

방문 순서는 1-2-3-4-5이다.

// 방문여부를 저장할 배열
boolean[] check = new boolean[n + 1];
// BFS 탐색을 위해 Queue를 이용한다.
Queue<Integer> queue = new LinkedList<Integer>();
// 1부터 탐색을 시작하기 위해 스택에 1을 넣어주고 방문 배열을 true로 변경해준다.
check[1] = true;
queue.add(1);

// 큐가 완전히 빌때까지 탐색한다.
while (!queue.isEmpty()) {
	int x = queue.peek();
	for (int j = 0; j < adj[x].size(); j++) {
		int v = adj[x].get(j);
		// 현재 있는 정점(=큐의 peek값)에서 방문할 수 있는 모든 정점을 큐에 담고 방문한다.
		if (!check[v]) {
			queue.add(v);
			check[v] = true;
		}
	}
}