Graph그래프

그래프(Graph)는 정점(Vertex) 과 간선(Edge) 으로 구성된 비선형 자료구조다. 소셜 네트워크, 지도, 네트워크 경로, 의존성 관계 등 실세계의 복잡한 관계를 모델링하는 데 사용된다.

그래프의 종류

그래프 표현

# 인접 리스트 (메모리 효율적, 희소 그래프에 적합)
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 4],
    3: [1],
    4: [2]
}

# 인접 행렬 (O(1) 간선 확인, 밀집 그래프에 적합)
matrix = [
    [0, 1, 1, 0, 0],
    [1, 0, 0, 1, 0],
    [1, 0, 0, 0, 1],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0]
]

그래프 탐색

• •BFS (너비 우선 탐색): 최단 경로
• •DFS (깊이 우선 탐색): 연결 요소, 위상 정렬

주요 알고리즘

관련 개념

• •BFS — 그래프 너비 우선 탐색
• •DFS — 그래프 깊이 우선 탐색
• •이진 트리 — 그래프의 특수한 형태
• •동적 프로그래밍 — 그래프 최단 경로 DP

참고문헌

• •Cormen et al. Introduction to Algorithms — Chapter 22
• •Sedgewick & Wayne. Algorithms, 4th Ed.