[알고리즘] 그래프 알고리즘 (BFS / DFS)

그래프란?

---

현상이나 사물을 정점과 간선으로 표현한 것. 두 정점이 간선으로 연결되어 있으면 인접하다고 한다.

구현 방식

---

그래프는 주로 두가지 방식으로 구현된다.

1. 연결 리스트를 이용한 인접 리스트 방식

간선의 개수만큼 메모리가 필요로 하지만 인접 행렬에 비해서 O(v)의 시간복잡도를 가진다.

 

2. 2차원 배열을 이용하는 인접 행렬 방식

메모리 공간을 많이 필요로 하는 대신 노드간 간선의 비용을 구하는 시간이 O(1)의 시간복잡도를 가진다.

 

3. N개의 연결 배열로 표현한 인접 배열 방식

메모리 사용량을 절감하면서 포인터 오버헤드 감소, 두 정점의 인접 여부를 체크하는 시간을 절감한다.

 

그래프 탐색 알고리즘

---

대표적인 두 가지 방법

- 너비우선탐색 (BFS)

- 깊이우선탐색 (DFS)

 

너비우선탐색 (BFS)

BFS는 깊이 우선 탐색과는 달리 노드v에 인접한 모든 노드를 방문한 다음 노드 v에 인접한 노드 중 하나를 다시 택하여 다시 너비 우선 탐색을 계속하는 방법이다.

 

특징

- 직관적이지 않다. BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.

- BFS는 재귀적으로 동작하지 않는다.

- 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.

깊이우선탐색 (DFS)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프에서 한 방향으로 탐색을 진행하다가 더 이상 탐색을 진행할 수 없는 상황이 되면, 가장 최근데 방문했던 정점에서 다시 탐색을 진행하는 방법이다.

 

특징

- 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.

- 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

- 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.

 

참고 자료

---

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

https://velog.io/@dnrgus1127/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98