BFS DFS 차이

DFS와 BFS 는 그래프 탐색 알고리즘입니다.

DFS 는 깊이 우선 탐색으로 시작 노드부터 각각의 분기들을 순차적으로 완벽 탐색하는 알고리즘입니다.

 

시작 노드에서부터 최대한 깊이 들어가면서 그래프를 탐색합니다.

한 경로를 끝까지 탐색한 후, 되돌아와서 다른 경로를 탐색합니다.

스택 또는 재귀 함수를 사용하여 구현할 수 있습니다.

 

노드의 수 V, E는 간선의 수를 나타냅니다.

시간복잡도 시간 복잡도는

 

• 인접 리스트를 사용하는 경우 각 노드와 그 인접한 간선들을 한 번씩 방문하므로 O(V + E)입니다.
• 인접 행렬을 사용하는 경우 모든 노드를 방문하고 간선을 확인하므로 O(V^2)입니다.

 

 

BFS 는 시작 노드로부터 인접한 노드들을 먼저 탐색하는 탐색 알고리즘입니다.

큐를 사용하여 먼저 발견된 노드들에게 우선 탐색권을 주어 구현 할 수 있습니다.

모든 인접한 노드를 우선 탐색하므로 너비 우선 탐색은 목표 노드와 시작 노드 사이의 최단 경로를 찾을 때 유용합니다.

• 인접 리스트를 사용하는 경우 각 노드와 그 인접한 간선들을 한 번씩 방문하므로 O(V + E)입니다.
• 인접 행렬을 사용하는 경우 모든 노드를 방문하고 간선을 확인하므로 O(V^2)입니다.