[Algorithm] 그래프 기본 개념과 그래프 탐색(BFS, DFS)

Graph란 무엇일까?

Graph는 일련의 노드(node, vertex, 정점) 집합 V와 엣지(edge, 간선) 집합 E로 구성된 자료구조이다. 보통 정점에는 Data가 들어가고, 간선은 그 Data들 간의 관계를 표현한다.

그래서 G = (V, E) 와 같이 표현할 수 있다.

간선으로 연결된 두 정점은 관계가 있다고 말할 수 있으며, 이를 인접(Adjacent)하다고 한다.

Graph의 종류

무향 그래프
간선에 방향이 없는 그래프로, 가장 기본적인 형태의 그래프이다.

가중 그래프
간선에 가중치가 존재하는 그래프로, 거리나 친밀도 등 수치 등 관계의 수치를 표현할 수 있다.

방향 그래프(유향 그래프)
간선에 방향이 존재하는 그래프

가중 방향 그래프
간선에 방향과 가중치가 모두 존재하는 그래프

Graph의 표현 방법

인접 행렬
n개의 정점을 가지는 그래프를 n*n 행렬 A[][]로 표현할 수 있다. 정점 i와 정점 j 사이에 간선의 존재 여부를 A[i][j]에 기록하며, 가중치를 표현할 수 있으며 간선이 존재하지 않는 경우 0 또는 무한을 이용해 표현 가능하다.

인접 행렬은 n제곱의 공간을 필요로 하는데, 두 정점 간의 인접성이 존재하는 경우보다 존재하지 않는 경우가 훨씬 많기 때문에 공간 낭비가 심하다.

 

인접 리스트
n개의 정점을 가지는 그래프를 n개의 연결 리스트로 표현한다. 정점 i에 연결된 정점들은 연결 리스트 i로 관리하며, 가중치가 있으면 함께 기록한다.

인접 리스트의 경우 특정 정점간의 인접성을 체크하는 과정이 비효율적이다.

 

인접 배열
n개의 정점을 가지는 그래프를 배열로 표현한다. 각 노드에 인접 정점 수를 명시하여, 필요한 부분까지 배열을 탐색하도록 한다.

배열을 정렬된 상태로 만들면 이진 탐색을 사용할 수 있기 때문에 |log2 K| + 1번 이내의 비교로 인접성을 확인할 수 있다.

 

인접 해시 테이블
n개의 정점을 가지는 그래프를 n개의 해시 테이블로 표현한다. 인접 배열에서의 2배정도 되는 크기로 해시테이블을 만든다면 인접성의 확인을 훨씬 빠르게 할 수 있다.

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

그래프에서 모든 정점을 방문해야 할 때가 자주 있는데, 이를 그래프 탐색이라고 한다. 그래프 탐색의 대표적인 방법으로 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)가 있는데, 우선 BFS에 대해서 알아보자.

 

직관을 돕기 위해 BFS를 설명한 그림부터 살펴보자.

Root Node인 0부터 출발하여 Root로부터 인접한 Node들부터 탐색하고, 점점 탐색 범위를 넓혀나가고 있다. 이런 점에서 이러한 그래프 탐색 방식을 너비 우선 탐색이라고 부른다.

 

구현
BFS를 구현하기 위해서는 Queue를 이용할 수 있다.
대상이 무방향 그래프라고 가정할 때, 기본 원리는 정점을 처음으로 방문할 때 큐에 삽입하고, 큐에정점을 하나씩 Dequeue 하면서 그에 인접한 정점들을 큐로 삽입하는 식으로 진행한다.

이는 큐가 빌 때까지 지속하며, 새로운 원소를 큐에 삽입할 때에는 이미 방문한 정점이 아닌 경우에만 삽입해 준다.

 

활용
세상의 모든 사람이 지닌 친분관계를 그래프로 나타냈을 때, 특정인 A와 B 사이 간선의 최단 경로를 구할 때 사용해줄 수 있다.

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

깊이 우선 탐색은 앞선 너비 우선 탐색과는 달리 Root Node부터 시작하여 가장 깊은 곳까지 탐색한 후 돌아서 모든 정점을 방문하는 방법이다.

위의 그림과 같이 깊이 우선 탐색에서는 한 쪽 노드를 선택하면 그 노드로부터의 가장 깊은 곳까지 탐색한 후 동일 높이의 노드를 탐색한다.

 

구현
DFS를 구현하기 위해서는 후입선출의 자료구조인 스택을 이용한다.
기본 원리는 정점을 처음 방문할 때 스택에 삽입하고, 해당 스택에서 방문할 수 있는 vertex를 탐색하며 방문한 다음에, 방문할 수 있는 vertex가 더이상 존재하지 않을 때 스택에서 제거해주는 것이다.

구현에서는 스택 자료구조를 직접 이용해줄 수도 있고, 재귀 호출을 통해 스택을 간접적으로 사용해줄 수도 있다.

 

특징
BFS에 비해 저장공간의 필요성이 적고, 찾아야 할 노드가 깊은 단계에 있을 수록 유리하다.

---

다음에 공부해볼 것

실제로 BFS, DFS 알고리즘을 구현해보고, 이를 활용하는 문제를 풀어보기!

 

참고

https://velog.io/@vagabondms/DFS-vs-BFS