DFS , BFS

[그래프]

그래프는 노드 혹은 정점이라 불리는 객체들의 모음과 이 객체들을 잇는 간선의 모음의 결합을 뜻한다.

이들 사이의 연결을 뜻하는 간선은 노드들을 연결하며 간선의 방향성에 따라 단방향 그래프, 양방향 그래프로 나눌 수 있고 또 간선의 가중치를 기준으로 할경우 연결 그래프와 가중치 그래프로 나눌 수 있다. 

 

그래프 내에서 각 정점의 인접 관계를 나타내는 행렬을 인접행렬 그래프라고 하는데 2차원 배열을 출발정점과 도착정점으로 표현할 수 있다.

이 인접행렬 그래프를 사용함으로써 얻는 장점은 두 노드간의 연결 여부를 상수 시간 O(1)에 확인할 수 있다는 점이다. 연결을 확인하고자 하는 좌표값이 true인지 false인지, 즉 연결 되었는지 여부를 인덱스로 확인할 수 있기 때문에 연결 여부를 즉각적으로 알 수 있다.

또한 bool이 아닌 수를 포함하는 자료형으로 2차원 배열을 나타낼 경우 가중치를 행렬의 값으로 표현할 수 있기 때문에 두 노드 사이의 거리나 비용을 나타내는 데에 효과적이다.

 

하지만 단점 또한 존재한다. 노드의 수가 많을수록 많은 메모리를 필요로 하는데 이는 특히 노드들 사이의 실제 간선의 수가 적을 때 두드러진다. 실제 연결되어 있지 않은 간선도 배열에 모두 연결되지 않음을 표시해야하기 때문에 간선이 적을 때는 효율적이지 않다.

 

양방향 연결 그래프의 경우 (n,n)좌표들을 잇는 선을 기준으로 대칭되는 좌표가 서로 같은 값을 같는다.

단방향으로 가중치를 준 그래프이다

 

 

 

이러한 방식으로 구현된 그래프를 탐색하는 데에 깊이 우선 탐색(DFS) 알고리즘과 너비 우선 탐색 (BFS) 알고리즘을 사용할 수 있다. 이 두 알고리즘으로 그래프 내의 모든 노드를 방문할 수 있다.

 

[DFS(깊이 우선 탐색)]

DFS는 그래프의 분기를 만났을 때 해당 분기를 끝까지 진행하여 최대한 깊이 내려간 뒤 , 분기의 탐색을 마쳤을 때 다음 분기를 탐색하는 과정을 거친다.

해당 과정을 모두 끝마쳐야 바로 다음에 진행할 과정을 거치기 때문에 스택(Stack) 자료구조나 재귀 함수를 통해 구현할 수 있다. 

 

탐색을 하고자 하는 그래프

스택을 사용한 DFS 구현

 

 

 

 

재귀 함수를 사용한 DFS 구현. 스택에 함수 호출을 쌓아가며 작동해 들어간다는 점에서 스택 자료구조를 사용한 방식과 작동원리는 같다.

 

 

 

[BFS(너비 우선 탐색)]

 

BFS는 그래프의 분기를 만났을 때 해당 단계의 모든 분기를 탐색한 뒤,  다음 깊이의 분기를 탐색하게 된다. 

즉 시작 노드로부터 인접한 노드들을 먼저 탐색한 후  해당 노드들의 인접한 노드들을 순차적으로 탐색하는 방식을 가지는데 이는 큐(Queue) 자료구조를 사용하여 구현할 수 있다.

 

 

시작점 0을 기준으로 연결되어 있는 3, 4를 접근하고 이후 연결되어 있는 노드들을 단계적으로 방문하게 된다.

 

 

 

 

 

 

 

 

위 그래프를 예시로 DFS와 BFS의 작동 순서를 보자면 DFS의 경우 해당 분기에서 호출 스택이 쌓이는 방식으로 최하단 부분에 도달하면 바로 이전 분기로 돌아와 가지 않았던 방향으로 진입하기 때문에 A -> B -> D -> E -> C -> F의 순서로 방문하게 된다. 

 

반면 BFS의 경우는 A에서 다음 노드들인 B,C를 큐에 집어 넣고 A에 인접한 모든 노드들의 확인이 끝나면 큐에 제일 먼저 들어간 B를 꺼내어 B에 인접한 D,E를 큐에 넣는 식으로 F까지 모든 노드들을 큐에 집어넣어 꺼내는 방식을 반복하게 된다.

따라서 A -> B -> C -> D -> E -> F 의 순서로 방문하게 된다.

 

DFS, BFS의 경우 그래프의 모든 정점을 순회할 수는 있지만 특정 시작점에서 목적지까지의 최소 거리를 나타내지는 않는데 이러한 목적을 달성하기 위해 모든 정점을 방문하여 최단 거리를 구하는 다익스트라 알고리즘과 휴리스틱 알고리즘을 사용하여 예상 거리를 구하는 A* 알고리즘도 존재한다.

 

이렇게 BFS와 다익스트라, A*는 각자 장단점과 특징이 있다.