그래프란?
- *정점(Vertex)과 간선(Edge)**으로 구성된 자료구조
- 정점 간의 연결 관계(네트워크)를 표현
- 방향, 가중치, 연결성에 따라 다양한 그래프 형태 존재
핵심 용어
| 용어 | 의미 |
|---|
| Vertex (정점, 노드) | 데이터를 나타내는 단위 |
| Edge (간선, 아크) | 정점 간의 연결 |
| Directed | 방향이 있는 간선 (A → B) |
| Undirected | 방향이 없는 간선 (A — B) |
| Weight | 간선에 부여된 비용/거리 |
| Degree | 정점에 연결된 간선 수 (진입차수 / 진출차수) |
그래프의 종류
| 분류 기준 | 종류 | 설명 |
|---|
| 방향성 | 방향 그래프 / 무방향 그래프 | 간선의 방향 유무 |
| 가중치 | 가중치 그래프 / 무가중치 그래프 | 간선에 값 부여 여부 |
| 연결 여부 | 연결 / 비연결 | 모든 노드가 연결되어 있는지 |
| 순환 여부 | 순환 그래프 / 비순환 그래프 | 사이클 존재 여부 |
| 특수 구조 | 트리, DAG | 트리 = 비순환 연결 그래프, DAG = 방향 + 비순환 |
그래프 구현 방법 (Python 기준)
인접 행렬 (Adjacency Matrix)
n = 4
graph = [[0]*n for _ in range(n)]
graph[0][1] = 1
- 메모리: O(N²)
- 모든 간선 확인 빠름
- 간선이 적을 땐 비효율적
인접 리스트 (Adjacency List)
graph = [[] for _ in range(4)]
graph[0].append(1)
- 메모리: O(N + M)
- 연결된 노드만 탐색 가능
- 일반적으로 선호되는 방식
딕셔너리 기반
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': [],
'D': []
}
시간 복잡도 비교
| 구현 방식 | 메모리 | 탐색 속도 |
|---|
| 인접 행렬 | O(N²) | 모든 정점 간 간선 확인 O(1) |
| 인접 리스트 | O(N + M) | 연결된 노드만 탐색 O(연결 수) |
실전 알고리즘 예시
| 알고리즘 | 설명 |
|---|
| DFS / BFS | 정점 방문 순회 |
| 다익스트라 | 가중치 있는 최단 경로 |
| 위상 정렬 | 방향 그래프 + 진입 차수 |
| 연결 요소 | 비연결 그래프의 개수 파악 |
| 사이클 탐지 | DFS + 방문 체크 |
Python vs C 구현 차이
| 항목 | Python | C |
|---|
| 리스트 | 리스트, 딕셔너리 | 배열, 포인터 배열 |
| 동적 메모리 | 자동 관리 | malloc, free 필요 |
| DFS/BFS | 스택, 큐 모듈 활용 | 직접 큐/스택 구현 필요 |
| 문자열 처리 | 편리한 인덱싱 | 포인터, 문자열 비교 직접 구현 |
자주 나오는 개념 정리
| 개념 | 설명 |
|---|
| 인접(adjacent) | 직접 연결된 노드 |
| 연결 요소 | 그래프 내 끊어진 연결 블록 수 |
| 진입 차수 / 진출 차수 | 들어오는 간선 / 나가는 간선 수 |
| 경로(Path) | 정점들의 연결된 순서 |
| 사이클(Cycle) | 출발점과 도착점이 같은 경로 존재 여부 |
핵심 요약
- 그래프는 정점(Vertex) + 간선(Edge)로 구성
- 구현은 대부분 인접 리스트 사용
- 문제 조건에 따라 방향성/가중치/연결성 확인 필수
- 실전 문제는 그래프 탐색 + 자료구조 구현 능력이 핵심
- DFS, BFS, 다익스트라, 위상정렬 등 그래프 알고리즘과 연결됨
