그래프

그래프의 핵심 개념

기본 용어

• 정점(Vertex, V): 객체(사람, 위치, 상태 등).
• 간선(Edge, E): 정점 간 관계/이동 가능성.
• 차수(Degree): 한 정점에 연결된 간선 수.
• 경로(Path): 정점들을 따라 이동한 순서.
• 사이클(Cycle): 시작 정점으로 다시 돌아오는 경로.
• 연결 요소(Connected Component): 서로 도달 가능한 정점들의 묶음.

그래프 분류

구분	의미	예시
무방향 그래프	간선에 방향 없음 (u <-> v)	친구 관계
방향 그래프	간선에 방향 있음 (u -> v)	팔로우, 일방통행
가중치 그래프	간선마다 비용/거리 존재	길찾기, 네트워크 비용
비가중치 그래프	간선 비용을 모두 1로 취급	연결 여부 탐색

트리와의 관계

항목	트리	일반 그래프
사이클	없음	있을 수 있음
루트 개념	있음(보통)	없음(임의 시작)
정점 관계	계층적	비계층적(대등)
연결성	항상 연결(정의상)	끊겨 있을 수 있음

• 트리 = 사이클 없는 연결 그래프로 볼 수 있습니다.

게임/실무 관점 예시

예시	정점	간선	비고
소셜 네트워크	사람	친구 관계	무방향
지하철 노선	역	구간	거리 = 가중치
MMO 맵	지역/타일	이동 경로	지형 비용 = 가중치
도로망	교차로	도로	일방통행 = 방향 그래프

---

그래프 표현 방식 (핵심)

인접 리스트 (Adjacency List)

• 구조: adj[u]에 u와 연결된 정점만 저장.
• 형태:
  • 비가중치: vector<vector<int>>
  • 가중치: vector<vector<pair<int,int>>> ({to, cost})
• 장점: 희소 그래프에서 메모리 효율이 매우 좋음.

int V = 6;
vector<vector<int>> adj(V);

// 무방향 간선 (0-1), (0-3), (1-2), (1-3)
adj[0].push_back(1); adj[1].push_back(0);
adj[0].push_back(3); adj[3].push_back(0);
adj[1].push_back(2); adj[2].push_back(1);
adj[1].push_back(3); adj[3].push_back(1);

복잡도(대표 연산):

• 메모리: O(V + E)
• 정점 u의 이웃 순회: O(deg(u))
• (u, v) 연결 여부 확인: O(deg(u)) (정렬/해시 없으면 선형 탐색)

인접 행렬 (Adjacency Matrix)

• 구조: matrix[u][v]에 연결 여부/비용 저장.
• 비연결 값 예: -1, INF, 0(문맥에 따라 선택).
• 장점: 연결 여부 확인이 즉시 O(1).

int V = 6;
vector<vector<int>> matrix(V, vector<int>(V, -1)); // -1 = 연결 없음
for (int i = 0; i < V; i++) matrix[i][i] = 0;

matrix[0][1] = matrix[1][0] = 15;
matrix[0][3] = matrix[3][0] = 35;
matrix[1][2] = matrix[2][1] = 20;

복잡도(대표 연산):

• 메모리: O(V^2)
• (u, v) 연결 여부 확인: O(1)
• 정점 u의 이웃 순회: O(V) (행 전체 스캔)

간선 리스트 (Edge List)도 기억

• 구조: 간선을 한 줄씩 저장 (u, v, w).
• 예: vector<tuple<int,int,int>> edges;
• 활용: 크루스칼, 벨만-포드처럼 간선 전체 순회가 핵심인 알고리즘.

---

resize vs reserve (그래프에서 실수 포인트)

Step 1. 차이 정리

함수	size 변화	capacity 변화	요소 접근 가능 여부
resize(n)	바뀜	보통 증가	0 ~ n-1 접근 가능
reserve(n)	그대로	확보	size는 그대로라 접근 불가

그래프 코드에서 왜 중요?

• vector<vector<int>> adj; 상태에서 adj[u].push_back(v) 하려면
  먼저 adj.resize(V)가 필요합니다.
• adj.reserve(V)만 하면 바깥 벡터의 size는 0이라 adj[u] 접근 시 오류 위험이 있습니다.

int V = 6;
vector<vector<int>> adj;

adj.resize(V);   // 정점 개수만큼 "실제 생성"
adj[0].push_back(1); // OK

reserve를 쓰는 올바른 위치

• 바깥 벡터: adj.reserve(V) (재할당 감소 목적)
• 안쪽 벡터: 예상 차수가 크면 adj[u].reserve(k)로 미리 확보 가능

---

인접 리스트 vs 인접 행렬 (선택 기준)

비교표

항목	인접 리스트	인접 행렬
메모리	O(V + E)	O(V^2)
연결 확인 (u,v)	O(deg(u))	O(1)
이웃 순회	O(deg(u))	O(V)
간선 추가/삭제	유연	단순하지만 메모리 큼
적합한 그래프	희소 그래프	밀집 그래프

선택 규칙 (실무형)

1. 정점 수가 크고 간선이 적다 -> 인접 리스트
2. 연결 여부 질의가 매우 많다 -> 인접 행렬
3. 메모리 제한이 빡빡하다 -> 인접 리스트 우선
4. E가 V^2에 가깝다 -> 인접 행렬 고려

알고리즘과의 궁합

• DFS/BFS: 둘 다 가능하지만, 보통 인접 리스트가 더 효율적
• 다익스트라/A*: 희소 그래프 + 우선순위 큐 조합에서 인접 리스트가 일반적
• 플로이드-워셜(모든 쌍 최단거리): 행렬 표현과 궁합이 좋음

---

체크리스트 (복습용)

• 그래프가 방향/무방향인지 먼저 구분했는가?
• 가중치가 필요한 문제인지 확인했는가?
• 표현 방식을 문제 규모(V, E)에 맞게 선택했는가?
• resize와 reserve를 헷갈리지 않았는가?
• 끊긴 그래프 가능성을 고려했는가? (Part 6의 DfsAll)

---