DFS, BFS

 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)은 대표적인 그래프 탐색 알고리즘이다. 두 알고리즘은 이름 그대로 깊이와 너비를 기준으로 그래프의 모든 노드를 순회하며 원하는 값을 찾는다.

 

 먼저 그래프가 무엇인지 알아보자.

 그래프는 정점과 간선으로 이루어진 비선형적 데이터 구조이다. 그래프를 표현하는 방법은 두가지가 있다.

인접 행렬 표현

 인접 행렬은 그래프를 0과 1의 행렬로 표현하는 방식이다.

 그래프에 n개의 정점이 있다면 n*n 행렬을 만든다. 그리고 정점 i에서 j로 가는 간선이 있는 경우 행렬의 (i, j) 요소를 1로 표시하고, 간선이 없는 경우 (i, j) 요소를 0으로 표시한다.

 예를 들어 위의 그림에서 정점이 3개인 그래프를 3*3 크기의 행렬로 표현할 수 있다. 세 정점은 자기 자신을 제외한 다른 정점과 각각 이어져 있으므로, (i, i) 요소를 제외한 모든 요소를 1로 표현한다.

 

 만약 간선에 방향성이 있어 한 정점에서 다른 정점으로 일방적으로만 이동할 수 있다면 그 그래프를 방향 그래프라고 한다. 위의 예시에서 본 그래프는 간선에 방향이 없기 때문에 무향 그래프라고 한다.

 무향 그래프의 행렬 표현에서는 모든 요소가 주대각선에 대하여 대칭이지만, 만약 그래프가 유향 그래프라면 행렬 표현이 조금 달라진다.

 위의 예시와 같은 유향 그래프의 행렬 표현을 살펴보면, 행렬의 요소가 주대각선에 대하여 대칭이 아닌 것을 알 수 있다.

 정점 1에서 2로는 간선이 이어져 있지만, 2에서 1로는 간선이 이어져있지 않다. 그렇기 때문에 행렬의 (1, 2) 요소는 1이지만 (2, 1) 요소는 0이다.

인접 행렬 표현

 그래프를 표현하는 두번째 방법은 인접 리스트 표현이다.

 정점의 개수가 n인 그래프의 인접 리스트는 길이가 n인 배열로 표현한다. 이 배열의 각 인덱스는 그래프의 특정 정점을 나타낸다. 그리고 배열의 인덱스 i에 있는 항목에는 정점i에 인접한 정점들을 포함하는 연결 리스트가 들어 있다.

 위의 예시는 정점이 3개인 그래프를 인접 리스트로 표현한 것이다.

 배열의 각 인덱스에는 0, 1, 2번 정점과 간선으로 이어진 정점들의 연결 리스트가 들어있다.

 

 인접 행렬 표현도 마찬가지로 유향 그래프를 표현할 수 있다.

 위의 예시는 정점이 3개인 유향 그래프를 인접 리스트로 표현한다.

 0번 정점은 어떤 정점과도 연결되어있지 않기 때문에 인접 리스트의 0번 인덱스에는 어떤 값도 들어있지 않다. 하지만 1번 정점은 0번과 2번 정점과 연결되어 있으므로 0, 2가 들어 있는 연결 리스트가 들어 있다.

DFS(깊이 우선 탐색)

 DFS는 그래프의 모든 정점을 순회하기 위한 알고리즘이다. 한 정점에서부터 인접한 정점을 탐색할 때, 그 인접한 정점을 통해 연결된 모든 정점을 완전히 탐색한다. 노드를 여러 번 처리하는 것을 피하기 위해 방문 배열을 사용한다.

 

1. DFS를 수행하기 위해 두 개의 배열을 준비한다. 하나는 정점을 방문했었는지를 표시하는 방문 배열이고, 하나는 방문해야 할 인접 정점을 담아두기 위한 스택이다.
2. 탐색을 시작할 정점을 정한다. 시작 정점의 모든 인접한 정점을 스택에 담는다. 시작 정점에 방문 했음을 표시한다.
3. 스택의 맨 위 정점을 꺼낸다. 그 정점의 모든 인접한 정점을 스택에 담는다. 이 때, 이미 방문했던 정점은 제외해야한다. 그 정점에 방문 했음을 표시한다.
4. 3의 과정을 반복한다.
5. 더 이상 스택에서 꺼낼 정점이 없다면 탐색을 종료한다.

위 과정을 거치면서 3과 4사이에 값을 비교하는 연산을 끼워넣는다면 그래프에서 원하는 값을 찾을 수 있다.

BFS(너비 우선 탐색)

 너비 우선 탐색은 DFS와는 다르게 각 인접한 정점을 탐색할 때, 한 정점으로부터 연결된 다른 정점들을 탐색하기보다 먼저 인접한 정점들을 탐색한다.

 BFS는 DFS와는 다르게 스택이 아닌 큐를 사용한다.

1. BFS를 수행하기 위한 두 개의 배열을 준비한다. 하나는 정점을 방문했는지를 표시하는 방문 배열이고, 하나는 다음 방문해야 할 인접 정점을 담아두기 위한 큐이다.
2. 탐색을 시작할 정점을 정한다. 시작 정점에 인접한 모든 정점을 큐에 담는다. 시작 정점을 방문 표시한다.
3. 큐의 맨 앞에서 정점을 꺼낸다. 그 정점에 인접한 모든 정점을 큐에 담는다. 이 때, 이미 방문했던 정점은 제외한다. 꺼낸 정점을 방문 표시한다.
4. 3의 과정을 반복한다.
5. 더 이상 큐에서 꺼낼 정점이 없다면 탐색을 종료한다.

 DFS와 탐색 방법이 매우 유사하다. 다만 다음 조사할 정점을 담는 배열이 스택인지, 큐인지만 다를 뿐이다.