Explaining BFS and DFS

소개
그래프는 현실 세계의 다양한 문제를 모델링하기 위해 사용되는 중요한 자료 구조입니다. 그래프에서 특정한 요소를 찾거나 연결된 요소들을 조사하는 것은 그래프 탐색 알고리즘의 주요 목표입니다. 이 블로그에서는 너비 우선 탐색 (BFS)와 깊이 우선 탐색 (DFS)에 대해 자세히 알아보겠습니다.

BFS (너비 우선 탐색)
1.1 BFS
너비 우선 탐색은 그래프에서 가까운 정점부터 순차적으로 탐색하는 알고리즘입니다. 큐를 사용하여 구현되며, 큐에 인접한 정점을 추가하고 방문한 정점은 표시합니다.

1.2 BFS 구현 방법
BFS를 구현하기 위해 다음 단계를 따릅니다:

시작 정점을 큐에 추가합니다.
큐가 빌 때까지 다음을 반복합니다:
큐에서 정점을 제거하고 방문한 것으로 표시합니다.
인접한 정점을 큐에 추가합니다.
1.3 BFS 시간 복잡도
BFS의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수이고, E는 간선의 수입니다. BFS는 그래프를 탐색하는 데에도 적합한 빠른 알고리즘입니다.

1.4 BFS의 장점과 단점
BFS의 장점:

최단 경로를 찾을 수 있습니다.
무방향 그래프에서 모든 연결 요소를 탐색할 수 있습니다.
BFS의 단점:

그래프의 크기가 큰 경우 공간 복잡도가 증가할 수 있습니다.
그래프에 순환 경로가 있는 경우 무한 루프에 빠질 수 있습니다.
DFS (깊이 우선 탐색)
2.1 DFS 개요
깊이 우선 탐색은 그래프의 정점을 최대한 깊이 탐색한 후 다음 분기로 넘어가는 알고리즘입니다. 스택이나 재귀 함수를 사용하여 구현됩니다.

2.2 DFS 구현 방법
DFS를 구현하기 위해 다음 단계를 따릅니다:

시작 정점을 스택에 추가합니다.
스택이 빌 때까지 다음을 반복합니다:
스택에서 정점을 제거하고 방문한 것으로 표시합니다.
인접한 정점 중 방문하지 않은 정점을 스택에 추가합니다.
3.3 DFS 시간 복잡도
DFS의 시간 복잡도는 O(V + E)입니다. BFS와 같은 시간 복잡도를 가지지만, BFS와 달리 경로의 길이에 대한 정보를 제공하지 않습니다.

2.4 DFS의 장점과 단점
DFS의 장점:

그래프의 구조를 파악하기에 유용합니다.
재귀적인 구조를 갖고 있기 때문에 재귀 알고리즘에 적합합니다.
DFS의 단점:

무한 루프에 빠질 수 있습니다.
최단 경로를 찾지 못할 수 있습니다.
BFS와 DFS 비교
3.1 BFS와 DFS의 차이점
BFS와 DFS의 주요 차이점은 탐색 순서입니다. BFS는 너비(가까운 정점부터)를 우선적으로 탐색하는 반면, DFS는 깊이(최대한 깊게)를 우선적으로 탐색합니다.

3.2 BFS와 DFS의 응용
BFS와 DFS는 그래프 탐색 외에도 다양한 응용 분야에서 활용됩니다. 예를 들어, 네트워크 라우팅, 미로 찾기, 그래프 분석, 그리고 인공 지능 등에 사용될 수 있습니다.

결론
이 블로그에서는 BFS와 DFS의 개념과 구현 방법, 시간 복잡도, 장단점, 그리고 두 알고리즘의 차이점에 대해 알아보았습니다. 그래프 탐색 알고리즘은 다양한 문제를 해결하는 데에 핵심적인 역할을 수행하며, 알고리즘 이해를 위해 코드 예시와 시각적인 그림을 활용하는 것이 도움이 될 것입니다. 추가로, BFS와 DFS의 응용 분야와 그래프 탐색 알고리즘의 중요성을 강조하고 마무리하겠습니다.

 

4.1 구현

from collections import deque

# 너비 우선 탐색(BFS)
def bfs(graph, start):
    # 방문한 노드를 저장하기 위한 큐
    queue = deque([start])
    # 방문한 노드를 체크하기 위한 리스트
    visited = [False] * len(graph)
    # 시작 노드 방문 처리
    visited[start] = True

    while queue:
        # 큐에서 하나의 노드를 꺼내서 출력
        node = queue.popleft()
        print(node, end=' ')

        # 인접한 노드 중에서 방문하지 않은 노드를 큐에 삽입하고 방문 처리
        for adjacent_node in graph[node]:
            if not visited[adjacent_node]:
                queue.append(adjacent_node)
                visited[adjacent_node] = True

# 깊이 우선 탐색(DFS)
def dfs(graph, start, visited):
    # 현재 노드를 방문 처리
    visited[start] = True
    print(start, end=' ')

    # 인접한 노드 중에서 방문하지 않은 노드를 재귀적으로 방문
    for adjacent_node in graph[start]:
        if not visited[adjacent_node]:
            dfs(graph, adjacent_node, visited)

# 그래프
graph = [
    [],                 
    [2, 3, 8],          
    [1, 7],             
    [1, 4, 5],         
    [3, 5],        
    [3, 4],           
    [7],              
    [2, 6, 8],        
    [1, 7]              
]

# BFS
print("너비 우선 탐색(BFS):")
bfs(graph, 1)
print()

# DFS
print("깊이 우선 탐색(DFS):")
visited = [False] * len(graph)
dfs(graph, 1, visited)
print()

4.2 실행화면