DFS와 BFS

그래프는 정점과 간선으로 이루어진 자료 구조의 일종이다. 

 

 

그래프 탐색에 있어 DFS, BFS 방식이 있다. 

 

DFS - 깊이 우선 탐색

BFS - 너비 우선 탐색

 

두 탐색은 모든 정점을 한번만 방문한다는 같은 목표를 가지고 있는데 그 과정에서 탐색하는 방식의 차이가 있다. 

 

DFS는 스택을 사용하고, BFS는 큐를 사용한다. 

 

구현에 있어서 인접행렬 또는 인접리스트를 통해 구현할 수 있다. 

 

<인접행렬>

- 정점의 개수가 n개일때 n*n 2차원 배열

- 일반적으로 a라고 이름을 짓는다

- 인접행렬 값이 1이라면 정점간의 간선이 존재하는 것 , 0이라면 존재하지 않는 것

- O(V^2)

<인접리스트>

- 1에 연결되어있는 간선들을 A[1]에 저장, 2에 연결되어있는 간선들을 A[2]에 저장

- O(V+E)

 

 

 

 

 

[참고자료]

[그래프] DFS와 BFS 구현하기 :: 마이구미