[자료구조] 그래프(Graph)의 탐색 및 구현

 

📌 그래프(Graph)의 탐색

 

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적입니다. 원하는 값만 한 번에 찾고 싶지만 그래프의 데이터는 배열처럼 정렬이 되어 있지 않기 때문에, 원하는 자료를 찾으려면 하나씩 모두 방문하여 찾아야 합니다.

 

그래프의 탐색에는 크게 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)이 있습니다.

 

 

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

깊이 우선 탐색이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다.

 

깊이 우선 탐색

 

• 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것입니다.
• 방식은 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동하면 됩니다.
• 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용됩니다.
• 시간은 오래 걸릴지라도 모든 노드를 완전히 탐색 가능하다는 장점이 있습니다.

 

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

너비 우선 탐색이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다.

 

 

• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것입니다.
• 방식은 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동하면 됩니다.
• 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용됩니다.

 

3. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 비교

두 가지 탐색 방법 중에서 어떤 것을 선택해야하는지 고민이 생길 수 있는데 상황에 따라 어떤 방식이 장점이 있는지 확인해보겠습니다.

 

1. 그래프의 모든 정점을 방문해야 상황
   - 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 두 가지 방법 중 어느 것을 사용해도 상관없습니다.
   
   
2. 경로의 특징을 저장해둬야 하는 문제
   - 예를 들자면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 되는 문제와 같이 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용하는 것이 좋습니다. (BFS는 경로의 특징을 가지지 못함)
   
   
3. 최단 거리를 구해야 하는 문제
   - BFS를 사용하는 것이 좋습니다. 왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 검색할 시 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단 거리이기 때문입니다.
   
   
4. 나머지 상황들...
   - 검색 대상 그래프가 크다면 DFS
   ex) 한국에서 미국까지 이동하는 경로: BFS로 탐색하면 제일 첫 번째 경로가 미국행이라도 다른 모든 경로를 살펴보아야함.
   - 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

 

 

 

📌 그래프(Graph)의 구현 2가지

 

그렇다면 그래프를 어떤 형태로 구현할 수 있을까요?

 

그래프를 구현할 수 있는 방법에는 2가지가 있습니다.

그것은 바로 인접리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)입니다.

 

1. 인접 리스트(Adjacency List)

인접 리스트로 그래프를 표현하는 것이 가장 일반적인 방법입니다.

• 모든 정점(혹은 노드)을 인접 리스트에 저장합니다. 즉, 각각의 정점에 인접한 정점들을 리스트로 표시한 것입니다.

0: 1
1: 2
2: 0, 3
3: 2
4: 6
5: 4
6: 5

 

2. 인접 행렬(Adjacency Matrix)

인접 행렬은 N x N 불린 행렬(Boolean Matrix)로써 matrix[i][j]가 true라면 i -> j로의 간선이 있다는 뜻입니다.

• 0과 1을 이용한 정수 행렬(Integer Matrix)을 사용할 수도 있습니다.

if (간선 (i, j)가 그래프에 존재) {
	matrix[i][j] = 1;
} else {
	matrix[i][j] = 0;
}

 

 

 

 

 

.Reference

https://velog.io/@usreon/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%98-%ED%83%90%EC%83%89-%EB%B0%A9%EB%B2%95-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS%EA%B3%BC-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS

그래프의 탐색 방법, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

[자료구조] 그래프(Graph)란 - Heee's Development Blog