그래프 탐색(BFS & DFS)

그래프(Graph) 탐색

그래프는 일련의 노드(node, 정점 ; Vertex) 집합 V와 엣지(edge, 간선) 집합 E로 구성된 자료구조이다. 정점에는 Data가 들어가고, 간선은 그 Data들 간의 관계를 표현한다. 그래서 G = (V, E)와 같이 표현할 수 있다. 간선으로 연결된 두 정점은 관계가 있다고 말할 수 있으며, 이를 인접(Adjacent)하다고 한다. 

 

 그래프 탐색 문제는 어떤 하나의 그래프와 해당 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선을 타고 이동할 수 있는 정점들을 모두 찾아야 하는 문제를 의미한다. 이 문제를 해결하기 위한 그래프 탐색 알고리즘에는 너비 우선 탐색과 깊이 우선 탐색이 있다.   

 

 

그래프의 종류

 

무향 그래프

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

 

가중 그래프

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

 

방향 그래프(유향 그래프)

: 간선에 방향이 존재하는 그래프이다.

 

가중 방향 그래프

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

 

 

 

넓이 우선 탐색 (BFS : Breadth First Search)

:그래프의 시작점에서 너비가 가까운 점들부터 우선적으로 탐색하는 알고리즘. 큐를 사용.

*큐 : FIFO(First In First Out). 먼저 탐색되는 노드를 먼저 빼내어 인접한 점들을 보는 것에 유리하다.

 

<동작과정>

1. 시작점인 1번을 큐에 넣고 방문처리를 한다.

2. 1번을 꺼내고 인접한 정점인 2, 3, 4번을 큐에 넣고 방문처리를 한다.

3. 큐에서 2번을 꺼내고 2번과 인접하며 방문하지 않은 노드를 꺼내서 방문처리한다.

4. 큐에서 3번을 꺼내고 위와 같이 반복한다.

5. 더이상 큐에서 꺼낼것이 없을 때까지 반복하면 된다.

 

 

 

 

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

: 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 스택이나 재귀 함수를 사용.

* 재귀 함수 : 자기 자신을 다시 호출하는 함수

 

<동작 과정>

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

 

 

 

[BFS vs DFS 비교]

 

 

[참고]

https://jin1ib.tistory.com/entry/BFS-DFS-1

그래프 탐색 알고리즘(Graph Search Algorithm)