[Python] 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)

DFS (Depth-First Search)

깊이 우선 탐색은 한 경로를 끝까지 탐색한 후 다시 돌아와 다른 경로를 탐색하는 방식입니다. 

스택 자료구조나 재귀를 사용하여 구현됩니다.

 

DFS는 모든 경로를 탐색하므로 그래프의 깊이가 깊을 경우 적합합니다.

 

예시 코드

 

def dfs(graph, start):
    visited = set()  # 방문한 노드 집합
    route = []  # 탐색 경로
    stack = [start]  # 스택에 시작 노드 추가

    while stack:
        vertex = stack.pop()  # 스택의 맨 위 노드를 꺼냄
        if vertex not in visited:
            route.append(vertex)  # 경로에 추가
            visited.add(vertex)  # 방문 처리
            stack.extend(reversed(graph[vertex]))  # 인접 노드 스택에 추가 (LIFO 구조)
    return route

# 예제 그래프
graph = {
    0: [1, 2, 4],
    1: [0, 3],
    2: [0],
    3: [1, 5],
    4: [0],
    5: [3]
}

# DFS 수행
result = dfs(graph, 0)
print("DFS 결과:", result)

 

결과 예시

 

  0 - 1 - 3 - 5
   \   \
    2   4

 

 

1. 스택: [0], 방문: {}, 경로: []

 

2. 스택: [], 방문: {0}, 경로: [0]

인접 노드 [4, 2, 1] 추가 → 스택: [4, 2, 1]

 

3. 스택: [4, 2], 방문: {0, 1}, 경로: [0, 1]
인접 노드 [3] 추가 → 스택: [4, 2, 3]

 

반복하여 모든 노드를 방문

 

최종 결과: [0, 1, 3, 5, 2, 4]

 

BFS (Breadth-First Search)

 

너비 우선 탐색은 시작 정점에서 가까운 노드부터 탐색을 확장해 나가는 방식입니다.

큐 자료구조를 사용하여 구현됩니다.

 

BFS는 그래프의 최단 경로를 탐색하거나 계층 구조를 파악하는 데 적합합니다.

 

예시 코드

 

def bfs(graph, start):
    visited = set()  # 방문한 노드 집합
    route = []  # 탐색 경로
    queue = [start]  # 큐에 시작 노드 추가

    visited.add(start)  # 방문 처리
    while queue:
        vertex = queue.pop(0)  # 큐의 맨 앞 노드 제거
        route.append(vertex)  # 경로에 추가

        # 인접 노드 방문
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return route

# BFS 수행
result = bfs(graph, 0)
print("BFS 결과:", result)

 

BFS 수행 과정

 

1. 큐: [0], 방문: {}, 경로: []
2. 큐: [1, 2, 4], 방문: {0}, 경로: [0]
3. 큐: [2, 4, 3], 방문: {0, 1}, 경로: [0, 1]

 

반복하여 모든 노드를 방문

 

최종 결과: [0, 1, 2, 4, 3, 5]