그래프 탐색 알고리즘1 (DFS, BFS)

안녕하세요. 오늘은 그래프 탐색 알고리즘 중 가장 많이 사용되고 알려진 두 가지 방법에 대해 정리하겠습니다. 

 

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

- 개념

DFS는 그래프에서 깊이를 우선으로 탐색하는 알고리즘입니다. 시작점으로부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 즉, 한 분기를 끝까지 탐색한 후 다음 분기로 넘어가는 방식입니다. 이러한 방식으로 탐색하면, 마치 그래프에서 한 경로를 끝까지 탐색하다가 막다른 곳에 도달하면, 이전 분기로 돌아가서 다른 경로로 탐색하는 방식과 비슷합니다.

DFS는 스택 또는 재귀 함수를 이용하여 구현할 수 있습니다.

 

- 구현 방법

• DFS를 구현하는 방법은 크게 두 가지가 있습니다.
  • 스택(Stack)을 이용한 구현
  • 재귀(Recursion)를 이용한 구현

- 스택을 이용한 구현

• 스택을 이용한 구현은 다음과 같습니다.
  1. 시작 노드를 스택에 넣고 방문 처리를 합니다.
  2. 스택에서 노드를 하나 꺼내어 방문하지 않은 인접한 노드를 모두 스택에 넣고 방문 처리를 합니다.
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.
• 파이썬 예시코드입니다. 

def dfs(graph, start_node):
    visited = []
    stack = [start_node]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack.extend(graph[node] - set(visited))

    return visited

 

- 재귀를 이용한 구현

• 재귀를 이용한 구현은 다음과 같습니다.
  • 시작 노드를 방문 처리합니다.
  • 시작 노드와 인접한 노드 중에서 방문하지 않은 노드를 선택하여 재귀 호출합니다.
• 파이썬 예시코드입니다. 

def dfs_recursive(graph, start_node, visited):
    visited.append(start_node)

    for node in graph[start_node]:
        if node not in visited:
            dfs_recursive(graph, node, visited)

    return visited

 

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

- 개념

BFS는 그래프에서 너비를 우선으로 탐색하는 알고리즘입니다. 시작점으로부터 가까운 정점부터 먼 정점까지 차례대로 방문하는 방식입니다. 즉, 시작점에서부터 거리가 가까운 정점을 먼저 방문하고, 그 다음으로 거리가 더 멀어지는 정점들을 차례대로 방문하는 방식입니다. 이러한 방식으로 탐색하면, 그래프에서 두 정점 사이의 최단 경로를 찾는 문제 등에 유용합니다.

 

- 구현 방법

BFS는 큐(Queue)를 이용하여 구현할 수 있습니다.

1. 시작 노드를 큐에 넣고 방문 처리를 합니다.
2. 큐에서 노드를 하나 꺼내어 방문하지 않은 인접한 노드를 모두 큐에 넣고 방문 처리를 합니다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다. 

• 파이썬 예시코드입니다.

from collections import deque

def bfs(graph, start_node): 
visited = [] queue = deque([start_node])
while queue:
    node = queue.popleft()
    if node not in visited:
        visited.append(node)
        queue.extend(graph[node] - set(visited))

return visited