그래프(Graph)

개요

그래프(Graph)는 객체(정점, Vertex)와 이들 사이의 연결 관계(간선, Edge)를 표현하는 비선형 자료구조로, 소셜 네트워크, 지도, 통신망, 관계형 데이터 등 현실 세계의 다양한 구조를 표현하는 데 사용된다. 방향성, 가중치, 순환 여부에 따라 다양한 그래프가 존재하며, 탐색, 최단 경로, 최소 신장 트리, 위상 정렬 등의 알고리즘이 활용된다.

---

1. 그래프의 구성 요소

구성 요소	설명
정점(Vertex)	데이터를 저장하는 노드 (점)
간선(Edge)	정점 간의 연결 관계 (선)
인접 정점	특정 정점과 직접 연결된 정점
차수(Degree)	정점과 연결된 간선의 수

---

2. 그래프의 분류

분류 기준	유형	설명
방향성	방향 그래프	간선에 방향이 있음 (A → B)
	무방향 그래프	간선에 방향이 없음 (A — B)
가중치	가중치 그래프	간선에 비용/거리 값이 있음
	비가중치 그래프	간선에 값이 없음
순환성	순환 그래프	사이클 존재 가능
	비순환 그래프(DAG)	사이클이 없는 그래프

---

3. 그래프의 표현 방식

방식	설명	시간 복잡도
인접 행렬	2차원 배열, V×V	간선 확인 O(1), 메모리 낭비 가능
인접 리스트	각 정점이 연결된 정점 리스트를 가짐	간선 탐색 O(정점의 차수)

---

4. 파이썬 그래프 구현 예시 (인접 리스트)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

그래프는 딕셔너리로 구현하는 것이 가장 직관적이다.

---

5. 주요 그래프 알고리즘

알고리즘	설명	복잡도
DFS	깊이 우선 탐색	O(V + E)
BFS	너비 우선 탐색	O(V + E)
다익스트라	가중치 최단 경로	O(E log V) (힙 사용)
벨만-포드	음수 간선 포함 최단 경로	O(VE)
플로이드-워셜	모든 정점 간 최단 거리	O(V³)
크루스칼/프림	최소 신장 트리	O(E log V)
위상 정렬	DAG의 정렬된 순서 탐색	O(V + E)

---

6. 그래프의 활용 분야

분야	활용 예시
소셜 네트워크	친구/팔로우 관계 모델링
내비게이션	지점 간 경로 탐색, 도로 네트워크
웹 크롤링	하이퍼링크 구조 탐색
통신 네트워크	라우팅, 연결성 분석
데이터 분석	추천 시스템, 그래프 기반 클러스터링
컴파일러	의존성 그래프, 위상 정렬

---

7. 그래프 관련 용어 정리

용어	정의
경로(Path)	정점들을 순서대로 연결한 것
사이클(Cycle)	시작과 끝이 같은 경로
연결 그래프	모든 정점이 연결된 그래프
비연결 그래프	일부 정점이 고립된 그래프
DAG	방향성이 있고 사이클이 없는 그래프

---

8. 결론

그래프는 복잡한 관계와 구조를 효과적으로 표현할 수 있는 범용적인 자료구조다. 방향성, 가중치, 순환 여부에 따라 다양한 알고리즘이 적용되며, 현실 세계 문제를 모델링하는 데 매우 적합하다. 그래프 구조의 표현 방식과 DFS/BFS를 비롯한 핵심 알고리즘을 정확히 이해하면 대부분의 실전 문제를 효율적으로 해결할 수 있다.