Graph: DFS, BFS

SeongGyun Hong·2025년 2월 11일

BFS DFS Graph 알고리즘

Python

목록 보기

20/34

1. 그래프(Graph)란?

정의
정점(노드)와 간선(연결선)으로 이루어진 자료 구조를 말한다.
종류
- 무방향 그래프
  간선에 방향이 없음 (친구 관계)
- 방향 그래프
  간선에 방향 있음 (트위터 팔로잉)
- 가중치 그래프
  간선마다 가중치(거리, 비용 등)이 부여됨

2. Graph 탐색이란?

왜 하나요?
그래프 내의 모든 노드나 특정 노드를 방문하기 위하여
주요 방법론
- DFS ( 깊이 우선 탐색 )
  하나 잡고 끝까지 가보자!
- BFS ( 너비 우선 탐색 )
  초, 스텝 단위로 차근차근히 내려가보자

3. DFS (Depth-First Search)

원리
한 노드에서 시작하여 끝까지 깊게 들어간 후 더이상 들어갈 수 없다면 다시 돌아와서 다른길을 탐색한다.
구현
주로 재귀 함수나 스택(후입 선출 구조)를 사용함
특징
- 경로 탐색이나 모든 경우의 수 탐색에 유용
- 재귀 사용하는 경우에 스택 오버 플로우 주의

예시

def dfs(graph, node, visited):
    visited.add(node)
    print(node, end=" ")  # 방문한 노드 출력
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 간단한 무방향 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited = set()
dfs(graph, 'A', visited)  # 출력 예: A B D E F C

4. BFS (Beardth-First Search)

원리
시작 노드에서 가까운(레벨이 낮은) 노드부터 차례대로 탐색
구현
큐(Queue, FIFO 구조) 사용
특징
- 최단 경로 문제에 적합함
- 큐에 많은 노드가 쌓일 수 있으니 메모리 사용 고려

예시

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=" ")  # 방문한 노드 출력
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 간단한 무방향 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')  # 출력 예: A B C D E F