BFS (너비우선 탐색)

• Breadh First Search
• 그래프 탐색 알고리즘으로 같은 깊이의 정점부터 탐색하는 알고리즘

특징

• Queue를 이용하여 구현 가능하다.

• 시작 지점부터 가까운 정점까지 탐색한다.

• 시간 복잡도는 O(V + E)

  (V는 정점의 수, E는 간선의 수)

DFS (깊이우선 탐색)

• Depth First Search
• 깊은 정점부터 탐색하는 알고리즘

특징

• stack

  1. 깊이 위주로 stack에 push

  2. 갈곳이 없으면 pop 하고 탐색

  3. 갈곳이 po이후

• 시작 정점에서 깊은 것 부터 찾는다.

• 시간 복잡도는 O(V + E)

  (V는 정점의 수, E는 간선의 수)