알고리즘 : 완전 탐색 #2 (BFS, DFS)

그래프 탐색

---

마지막으로 그래프 탐색(Graph Traversal)이 있습니다.

그래프란, 어떠한 현상이나 사물을 아래 그림처럼 정점(vertex)과 간선(edge)로 표현한 것으로,

두 정점이 간선으로 연결되어 있으면 인접하다고 합니다.

그래프 또는 트리를 탐색하기 위해 BFS와 DFS라는 기법이 쓰이게 되는데,

BFS(Breadth-First Search, 너비 우선 탐색)란 방문한 정점에 인접한 정점들을 우선 방문하는 방식이고,

DFS(Depth-First Search, 깊이 우선 탐색)란 인접한 정점 중 하나를 방문하되 그 정점에 인접한 정점을 계속 방문하여, 더 이상 방문할 정점이 없을 때 다시 처음 방문했던 정점에 인접한 또 다른 정점을 방문하게 됩니다.

그림으로 나타내면 다음과 같습니다.

둘 다 0에서 시작했는데, BFS는 왜 1부터 시작하고 DFS는 왜 3부터 시작할까요?

그 차이는 큐(Queue)를 이용할 지, 스택(Stack)을 이용할 지에 달려 있습니다.

 

또한 두 방식 모두 배열 visited[n]을 이용하여 표현하는데, 자세한 쓰임은 아래에서 알아보겠습니다.

visited[i] = true : 방문하였음
visited[i] = false : 방문하지 않았음

---

BFS

---

그 중 BFS는 큐를 사용합니다. 큐는 FIFO(First in First out, 선입선출) 구조로, 먼저 들어온 데이터를 우선 처리합니다.

큐에는 앞으로 방문할 정점을 저장하며, 방문하게 되면 큐에서 삭제하고 visited[i]를 TRUE로 만듭니다.

먼저 시작할 정점(seed vertex) 0을 큐에 넣습니다.

큐에서 제일 앞에 있는 정점인 0을 방문하게 되는데,

0을 방문하면 0에 인접한 정점, 즉 0의 자식 노드를 큐에 삽입합니다.

또한 큐에서 0을 삭제하고, visited[0]=TRUE로 만듭니다.

큐에서 가장 앞에 있는 정점인 1을 방문하고,

1에 인접한 정점인 4를 큐에 삽입하고 1은 삭제하며 visited[1]=TRUE로 만듭니다.

이번에는 2를 방문할 차례이니 2를 삭제하고 2의 인접한 정점인 5를 삽입합니다.

또한 visited[2]=TRUE로 만들어줍니다.

3을 방문했는데, 인접한 정점이 5지만 이미 큐에 들어가 있죠?

따라서 큐에서는 삽입 없이 3의 삭제만 이뤄지고, visited[3]=TRUE로 만들어줍니다.

4를 방문할 차례니 큐에서 4를 삭제하고 인접한 정점 6을 삽입합니다.

또한 visited[4]=TRUE로 바꿔줍니다.

3과 마찬가지로 이미 6이 큐에 들어있으므로, 큐에서는 5의 삭제만 이뤄집니다.

visited[5]=TRUE로 바꿔줍니다.

6을 삭제하고, 또 인접한 정점이 없으므로 삽입이 이뤄지지 않습니다.

visited[6]=TRUE로 바꿔줍니다.

큐가 공백이 되었으므로 연산을 종료합니다.

BFS의 실제 알고리즘은 다음과 같습니다.

BFS(s) // 시작정점 s
	for(i←0; i<n; i←i+1) do {
		visited[i] ← false; // 모든 정점을 방문 안한 것으로 초기화
	}
	visited[s] ← true; // 시작정점 방문
	queue ← createQ(); 
	enqueue(queue, s); // seed를 큐에 삽입
	while (not isEmpty(queue)) do {
		j ← dequeue(queue); // 큐에서 하나를 뺌
		visit j; // 행동 (print)
		for (each k∈adjacency(j)) do { // 조건에 맞는 정점을 다시 enqueue
			if (visited[k] = false) then {
				enqueue(queue, k);
				visited[k] ← true;
			}
		}
	}
end BFS()

---

DFS

---

DFS는 스택을 사용합니다. 스택은 큐와 달리 LIFO(Last in First out, 후입선출) 구조로,

마치 프링글스처럼 마지막에 넣은 데이터를 최우선으로 사용할 수 있습니다.

DFS에서도 마찬가지로 방문할 정점을 스택에 저장하게 되며, 스택이 비면 연산을 종료합니다.

0의 인접 정점을 스택에 쌓게 되면, 큐와 달리 스택에선 마지막으로 쌓은 3이 최우선적으로 pop 됩니다.

3을 pop 한 후, 스택에 3의 인접 정점인 5를 넣습니다.

4를 pop 했을 때, 이미 스택에 들어있는 1, 2를 제외하면 4의 인접 정점이 없으므로

스택에 쌓인 차례대로 2, 1을 pop 하며 visited[i]를 바꿔줍니다.

이렇게 스택이 공백이 되었으므로 연산을 종료합니다.

DFS의 실제 알고리즘은 다음과 같습니다.

DFS(s)
	for(i←0; i<n; i←i+1) do {
		visited[i] ← false; // 모든 정점을 방문 안한 것으로 초기화
	}
	stack ← createStack(); // 방문할 정점을 저장하는 스택
	push(stack, s); // 시작정점 s를 스택에 저장
	while (not isEmpty(stack)) do { // 스택이 공백이 될 때까지...
		j ← pop(stack); // pop
		if(visited[j] = false) then { // j가 아직 미방문 정점이면
			visit j; // 방문하고
			visited[j] ← true; // visited[j]를 TRUE로
			for (each k∈adjacency(j)) do { // j의 인접 정점에서
				if (visited[k] = false) then // 미방문 한 정점은
					push(stack, k); // 스택에 push
			}
		}
	}
end DFS()