오늘 한 일
- 그래프 자료구조 개념 정리
- 그래프 표현 방법(인접 행렬/인접 리스트)과 탐색(DFS/BFS) 학습
배운 내용
그래프 기본
- 정점(vertex)을 간선(edge/link)으로 연결한 자료구조 — 연결 관계 표현
- 트리도 그래프의 일종
- 트리: 사이클 없음 + 상하 관계(계층적 구조)
- 그래프: 사이클 가능 + 상하 관계 없음 → 더 일반적인 연결 관계 표현
그래프 종류
- 연결 그래프: 임의의 두 정점 사이에 경로 존재 ↔ 비연결 그래프
- 방향 그래프 ↔ 무방향 그래프
- 가중치 그래프: 간선에 가중치(비용, cost) 부여. 양수·음수 모두 가능
- 서브 그래프: 특정 그래프의 정점·간선 일부로 이루어진 그래프
그래프 표현
- 인접 행렬: N×N 행렬,
<행, 열> = <출발 정점, 도착 정점>
- 연결 1 / 비연결 0, 가중치 그래프는 가중치 값으로 표기
- 무방향 그래프는 양방향 연결로 간주 → 행렬이 대칭
- 인접 리스트: 정점마다 연결된 정점들을 연결 리스트로 관리
| 인접 행렬 | 인접 리스트 |
|---|
| 공간 | O(V²) | O(V+E) |
| 두 정점 연결 확인 | O(1) | O(차수) |
| 유리한 경우 | 밀집 그래프 | 희소 그래프 |
그래프 탐색
- DFS(깊이 우선 탐색): 더 이상 방문할 정점이 없을 때까지 최대한 깊이 탐색 반복
- BFS(너비 우선 탐색): 가까운 정점부터 최대한 넓게 탐색 반복
- 구현: 방문 여부 배열 + 큐 (연결 정점 줄세우기)
- 시간 복잡도: 둘 다 인접 리스트 기준 O(V+E), 인접 행렬 기준 O(V²)
내일 할 것
- 정처기 실기 계산 문제풀이 시작 (6/22 접수 전 워밍업)