BFS, DFS

DFS (Depth First Search)

DFS는 깊이 우선 탐색 알고리즘으로, 특정한 경로를 따라 최대한 깊숙히 들어가면서 노드를 탐색하는 알고리즘입니다. 스택 자료구조 또는 재귀 함수를 통해 구현할 수 있습니다.

 

DFS 알고리즘은 시작 노드에서부터 한 방향으로 갈 수 있는 경로를 모두 탐색하고, 갈 수 있는 경로가 더 이상 없다면 다시 바로 이전 노드로 돌아와 다른 방향으로 다시 탐색합니다. 이러한 과정을 모든 노드를 방문할 때까지 반복합니다.

 

DFS 알고리즘의 시간 복잡도는 최악의 경우 모든 노드를 방문해야 하므로 O(V + E) 입니다.

BFS (Breadth First Search)

BFS는 너비 우선 탐색 알고리즘으로, 특정한 경로를 따라 이동할 때 너비를 우선으로 탐색하는 알고리즘입니다. 큐 자료구조를 통해 구현할 수 있습니다.

 

BFS 알고리즘은 시작 노드에서부터 인접한 노드를 모두 방문하고, 다음으로 인접한 노드를 방문하는 방식으로 동작합니다. 이러한 과정을 모든 노드를 방문할 때까지 반복합니다.

 

BFS 알고리즘의 시간 복잡도는 최악의 경우 모든 노드를 방문해야 하므로 O(V + E) 입니다.

DFS vs BFS

DFS와 BFS는 각각 깊이 우선 탐색과 너비 우선 탐색 알고리즘이며, 그 구현 방식과 탐색 순서가 다릅니다.

 

DFS는 시작 노드에서부터 한 방향으로 갈 수 있는 경로를 모두 탐색하고, 갈 수 있는 경로가 더 이상 없다면 다시 바로 이전 노드로 돌아와 다른 방향으로 다시 탐색합니다. 이에 비해 BFS는 인접한 노드를 모두 방문한 후에 다음으로 인접한 노드를 방문하는 방식으로 동작합니다.

 

따라서 DFS는 스택 자료구조 또는 재귀 함수를 통해 구현되며, BFS는 큐 자료구조를 통해 구현됩니다. 또한 DFS는 최대한 깊숙히 들어가면서 노드를 탐색하는 방식으로 동작하기 때문에 탐색한 경로를 되돌아가지 않는 경향이 있습니다.