DFS와 BFS의 차이점

DFS와 BFS는 그래프 탐색 알고리즘 중 두 가지 주요한 방법입니다. 이 두 알고리즘은 그래프 내의 노드와 엣지를 탐색하는 데 사용되며, 각자의 특징과 장단점이 있습니다.

 

 

DFS (깊이 우선 탐색)

1. 개요

DFS는 그래프 탐색을 수행하는 한 가지 방법으로, 더 깊은 노드로 들어가면서 탐색을 진행하는 방식입니다. 시작 노드에서 출발하여 한 경로를 끝까지 탐색한 후, 해당 경로의 모든 노드를 탐색합니다. 그 후, 다음 경로로 이동하여 다시 탐색을 진행합니다.

 

2. 특징

• 스택(Stack)이나 재귀(Recursion)를 이용하여 구현할 수 있습니다.
• 경로의 끝까지 탐색하고, 더 이상 탐색할 곳이 없으면 되돌아와 다음 경로를 탐색합니다.
• 깊은 경로에 먼저 도달하므로, 깊이 우선적으로 탐색됩니다.

3. 예시

다음은 그래프의 예시입니다.

 

   A
  / \
 B   C

 

만약 A에서부터 DFS를 시작한다면, 다음과 같은 순서로 노드를 탐색할 수 있습니다: A - B - C.

 

def dfs(node, visited):
    if not visited[node]:
        visited[node] = True
        print(node, end=" ")
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor, visited)

visited = [False] * num_nodes
dfs(start_node, visited)

 

BFS (너비 우선 탐색)

1. 개요

BFS는 그래프 탐색을 수행하는 또 다른 방법으로, 가까운 노드부터 탐색을 시작하며, 해당 노드와 인접한 모든 노드를 먼저 탐색합니다. 큐(Queue) 자료구조를 사용하여 구현됩니다.

 

2. 특징

• 큐(Queue)를 이용하여 구현할 수 있습니다.
• 시작 노드에서 인접한 노드를 먼저 탐색하고, 해당 노드의 인접한 노드를 탐색합니다.
• 가까운 노드에 먼저 도달하므로, 너비 우선적으로 탐색됩니다.

 

 

3. 예시

다음은 그래프의 예시입니다.

 

   A
  / \
 B   C

 

만약 A에서부터 BFS를 시작한다면, 다음과 같은 순서로 노드를 탐색할 수 있습니다: A - B - C.

 

from collections import deque

def bfs(start_node):
    visited = [False] * num_nodes
    queue = deque([start_node])
    while queue:
        node = queue.popleft()
        if not visited[node]:
            visited[node] = True
            print(node, end=" ")
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    queue.append(neighbor)

bfs(start_node)

 

결론

DFS와 BFS는 그래프 탐색 알고리즘으로, 각자 깊이 우선과 너비 우선으로 노드와 엣지를 탐색합니다. DFS는 스택이나 재귀를 통해 깊은 경로를 탐색하는 반면, BFS는 큐를 이용하여 가까운 노드부터 탐색합니다. 상황과 문제의 특성에 따라서 적절한 알고리즘을 선택하여 사용하면 좋습니다.