그래프 탐색 알고리즘 (Graph Traversal Algorithms)

10. 그래프 탐색 알고리즘 (Graph Traversal Algorithms)

**그래프 탐색(Graph Traversal)**은 그래프에서 정점들을 체계적으로 방문하는 과정입니다. 그래프 탐색 알고리즘은 **깊이 우선 탐색(DFS, Depth-First Search)**과 **너비 우선 탐색(BFS, Breadth-First Search)**으로 나눌 수 있습니다. 이들은 그래프 내의 경로 탐색, 최단 경로 찾기, 연결성 확인 등의 문제를 해결하는 데 중요한 역할을 합니다.

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

**깊이 우선 탐색(DFS)**은 그래프의 시작 정점에서부터 한 경로를 끝까지 탐색한 후, 더 이상 갈 곳이 없으면 되돌아와 다른 경로를 탐색하는 방식입니다. 이 방식은 재귀 또는 스택을 이용해 구현할 수 있습니다. DFS는 **순환적인 탐색**과 **미로 문제**와 같은 경우에 유리합니다.

DFS의 동작 방식

DFS는 다음과 같은 방식으로 동작합니다:

시작 정점에서 출발하여, 방문하지 않은 인접 정점으로 계속 이동합니다.
더 이상 이동할 인접 정점이 없으면, 이전 정점으로 돌아가서 다른 경로를 탐색합니다.
모든 정점을 방문할 때까지 이 과정을 반복합니다.

예제: 파이썬으로 DFS 구현

# 재귀를 이용한 DFS 구현
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    print(start, end=" ")  # 방문한 노드 출력

    # 인접 노드 방문
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 그래프 정의 (인접 리스트)
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
}

# DFS 실행
dfs(graph, 1)  # 출력: 1 2 4 5 3 6

이 예제는 파이썬을 사용하여 재귀적으로 DFS를 구현한 것입니다. DFS는 그래프의 깊은 부분부터 먼저 탐색하는 알고리즘입니다.

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

**너비 우선 탐색(BFS)**은 시작 정점에서 가까운 정점부터 차례대로 방문하는 방식입니다. BFS는 큐(Queue)를 이용하여 구현하며, **최단 경로 탐색**에 적합합니다. 이 방식은 그래프에서 경로의 길이가 중요한 경우에 많이 사용됩니다.

BFS의 동작 방식

BFS는 다음과 같은 방식으로 동작합니다:

시작 정점을 큐에 넣고, 해당 정점을 방문합니다.
큐에서 정점을 꺼내, 해당 정점과 인접한 모든 방문하지 않은 정점을 큐에 삽입합니다.
더 이상 방문할 정점이 없을 때까지 이 과정을 반복합니다.

예제: 파이썬으로 BFS 구현

from collections import deque

# BFS 구현
def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()  # 큐에서 정점을 꺼냄
        if vertex not in visited:
            print(vertex, end=" ")
            visited.add(vertex)

            # 인접한 정점을 큐에 추가
            queue.extend(graph[vertex])

# 그래프 정의 (인접 리스트)
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
}

# BFS 실행
bfs(graph, 1)  # 출력: 1 2 3 4 5 6

BFS는 큐를 이용해 구현되며, 시작 정점에서 가까운 정점부터 차례로 탐색합니다. 이 예제는 파이썬의 `deque`를 사용하여 BFS를 구현한 예시입니다.

10.3 DFS와 BFS의 차이점

DFS와 BFS는 모두 그래프 탐색 알고리즘이지만, 탐색 방식에서 큰 차이를 보입니다:

DFS: 깊은 곳부터 먼저 탐색하며, 재귀나 스택을 사용합니다. 특정 경로의 탐색이나 미로 찾기 문제에 유리합니다.
BFS: 가까운 곳부터 차례로 탐색하며, 큐를 사용합니다. 최단 경로를 찾는 문제에 유리합니다.

10.4 그래프 탐색 알고리즘의 응용

그래프 탐색 알고리즘은 다양한 문제 해결에 사용됩니다. 주요 응용 사례는 다음과 같습니다:

경로 탐색: 미로 찾기나 지도에서 경로를 찾는 문제에 사용됩니다. DFS는 가능한 경로를 모두 탐색하고, BFS는 최단 경로를 찾습니다.
최단 경로 탐색: BFS는 최단 경로를 찾는 문제에서 많이 사용되며, 다익스트라 알고리즘의 기초가 됩니다.
네트워크 연결성 확인: DFS와 BFS는 네트워크에서 노드들이 연결되어 있는지 확인하는 데 사용됩니다.
사이클 탐지: DFS는 그래프에서 사이클이 존재하는지 탐지하는 데 매우 유용합니다.

설화스터디 소프트웨어학과

[자료구조개론] 10. DFS,BFS 깔끔 완벽 설명