BFS, DFS 알고리즘 [알고리즘 이론]

 

 

 

 

BFS(Breadth-First Search, 너비 우선 탐색)와 DFS(Depth-First Search, 깊이 우선 탐색)에 대해 설명드리겠습니다. 이 두 알고리즘은 그래프를 탐색하는 가장 기본적인 방법입니다. 그래프는 노드(정점)들과 그 노드들을 연결하는 간선들로 구성되어 있습니다. BFS와 DFS는 이러한 그래프의 모든 노드를 방문하는 방법 중 하나입니다.

BFS(Breadth-First Search, 너비 우선 탐색)

BFS는 시작 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방식입니다. 이 알고리즘은 큐를 사용하여 구현할 수 있습니다. BFS는 다음과 같은 단계로 진행됩니다:

1. 탐색을 시작할 노드를 큐에 삽입하고 방문했다고 표시합니다.
2. 큐에서 노드를 하나 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문했다고 표시합니다.
3. 큐가 빌 때까지 2번을 반복합니다.

Python 코드 예시 (BFS)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
            queue.extend(set(graph[vertex]) - visited)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')

 

DFS(Depth-First Search, 깊이 우선 탐색)

DFS는 시작 노드에서 시작하여 가능한 한 깊이 있는 노드를 우선적으로 탐색하는 방식입니다. 이 알고리즘은 스택을 사용하거나 재귀 호출을 통해 구현할 수 있습니다. DFS는 다음과 같은 단계로 진행됩니다:

1. 탐색을 시작할 노드를 스택에 삽입하고 방문했다고 표시합니다.
2. 스택에서 노드를 하나 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 스택에 삽입하고 방문했다고 표시합니다.
3. 스택이 빌 때까지 2번을 반복합니다.

Python 코드 예시 (DFS)

def dfs(graph, vertex, visited=set()):
    if vertex not in visited:
        visited.add(vertex)
        print(vertex, end=' ')
        for neighbor in graph[vertex]:
            dfs(graph, neighbor, visited)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs(graph, 'A')

BFS는 최단 경로를 찾는 데 사용될 수 있으며, DFS는 사이클이나 연결 요소를 찾는 데 유용합니다. 각 알고리즘의 선택은 문제의 특성과 요구 사항에 따라 달라집니다.