BFS & DFS

그래프를 탐색할때, 하나의 정점에서 시작하여 그래프의 정점들을 방문하는데, 이때 그래프 탐색 방법(방문하는 방법)에 따라 BFS와 DFS로 구분할 수 있다.
이 둘은 공통적으로 다음과 같은 과정을 반복한다.

1. vertex 방문하기
2. vertex의 모든 adjacent vertex를 방문하여 탐색하기

BFS

Breadth First Search
level-order

• 어느 정점에서든 시작할 수 있다.

• 탐색을 시작할 노드를 enqueue한다. 탐색을 시작하면 dequeue한다. 인접한 노드들을 먼저 방문하여 queue에 enqueue하고, 순서대로 다시 인접 노드들을 다시 탐색한다.
  어느 정점에서 시작하느냐에 따라 다양한 BFS가 나올 수 있다.
  1,2,4,5,7,8,3,6,10,9
4,1,3,2,10,9,5,7,8,6
3,2,4,10,9,1,5,7,8,6

DFS

Depth First Search
preorder

• 어느 정점에서든 시작할 수 있다.

• 시작한 정점(1)을 stack에 push하고 탐색한다. 정점과 인접한 정점(2)을 방문하여 그 정점을 stack에 push하고 탐색한다. 인접 정점이 없을때까지 탐색한 후 stack을 pop하고, 가장 마지막 정점을 다시 탐색한다.

어느 정점에서 시작하느냐에 따라 다양한 DFS가 나올 수 있다.

1,2,5,6,7,8,3,10,9,4
3,2,5,6,7,8,1,4,10,9
3,4,1,2,5,6,7,8,10,9

https://www.youtube.com/watch?v=pcKY4hjDrxk