Graph

1. Graph 란?

정점(Vertext, Node) 과 간선(Edge) 의 집합으로 이루어진 자료구조

예 : 도시(정점) 와 도로(간선), 사람(정점) 과 친구 관계(간선), 서버(장점)와 연결(간선) 등

예시 :

정점: A, B, C, D  
간선: A-B, A-C, B-D 

⇒ 시각화 :

A --- B
|     |
C     D

---

2. Graph 의 종류

분류 기준	유형	설명
방향성	무방향 그래프	간선이 양방향 (A-B = B-A)
	방향 그래프	간선이 단방향 (A→B)
간선 가중치	가중치 그래프	간선에 비용/거리 등이 있음
	비가중치 그래프	간선에 비용 없음
자기 간선	루프 그래프	정점이 자기 자신과 연결된 간선이 있음
중복 간선	멀티 그래프	정점 사이에 여러 간선 허용
연결성	연결 그래프	모든 정점이 이어짐
순환성	사이클 그래프	순환(사이클)이 존재

---

3. Graph 표현 방법

1) 인접 행렬(Adjacency Matrix)

• 2차원 배열 사용 : graph[i][j] == 1 ⇒ i 에서 j 로 간선 존재

• 메모리: O(N^2)

• 장점 : 간선 여부 즉시 확인

• 단점 : 메모리 낭비가 심함(희소 그래프에 비효율적)

int[][] graph = new int[N + 1][N + 1];
graph[1][2] = 1;
graph[2][3] = 1;

2) 인접 리스트(Adjacency List)

• List<List<Integer>> 형태로 표현

• 메모리 : O(V + E) (공간 효율 높음)

• 장점 : 연결된 노드 순회에 적합

• 단점 : 간선 존재 여부 확인이 느릴 수 있음.

List<List<Integer>> graph = new ArrayList<>();

for(int i = 0; i <= N; i++) {
    graph.add(new ArrayList<>());
}

graph.get(1).add(2);
graph.get(2).add(3);

실무나 코테에서는 인접 리스트 + 우선순위 큐(PriorityQueue) 조합이 가장 흔함.

---

4. 그래프 관련 용어 정리

용어	의미
Vertex (정점)	그래프의 노드
Edge (간선)	노드 간의 연결
Degree (차수)	정점에 연결된 간선 수
In-degree / Out-degree	들어오는 / 나가는 간선 수 (방향 그래프에서)
Path (경로)	두 정점 사이의 연결된 정점들의 순서
Cycle (사이클)	시작점과 끝점이 같은 경로
Connected	연결되어 있는지 여부
Weight (가중치)	간선의 거리, 비용, 시간 등

---

5. Graph 알고리즘

✅ 탐색

• DFS (깊이 우선 탐색)

• BFS (너비 우선 탐색)

✅ 최단 경로

• Dijkstra (다익스트라)

• Bellman-Ford (음수 허용)

• Floyd-Warshall (모든 쌍 간 최단 거리)

✅ 최소 신장 트리

• Kruskal

• Prim

✅ 위상 정렬

• DAG(방향 비순환 그래프)에서 노드 순서 정렬

✅ 유니온 파인드 (Disjoint Set)

• 서로 다른 집합의 연결 여부 확인 (사이클 탐지)

---

6. Graph 는 어디에 쓰임?

• 지도 / 네비게이션 : 거리 계산, 최단 경로

• SNS : 친구 추천, 연결된 그룹 찾기

• 네트워크 : 라우팅, 회선 최소화

• 게임 : 이동 가능 영역, 퍼즐 탐색

• 스케줄링 : 작업 순서(위상 정렬)

• AI : 상태 공간 그래프 기반 경로 탐색