DFS & BFS

[JongHoooon]

DFS(Depth-First Search)

• 그래프에서 모든 노드를 방문 알고리즘으로 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
• 재귀와 스택을 사용해서 구현

BFS(Broad First Search)

• 그래프에서 모든 노드를 방문 알고리즘으로 인접한 노드를 먼저 탐색하는 방법으로 가까운 정점을 먼저 방분하고 멀리 떨어져 있는 정점을 나중에 방문한다.
• 큐를 사용해서 구현

용도

• BFS: 최단거리를 구하거나 거리가 가까운 경우

• DFS: 경로의 특징을 지정해줘야 하는경우 사용

• 참고