Graph

Graph

정점(Vertex)과 간선(Edge)으로 구성된 비선형 자료구조이다.

• 정점(Vertex) : 자료를 저장하는 단위 (노드라고도 함)
• 간선(Edge) : 두 정점을 연결하는 선. 정점 쌍 (u, v)로 표현

그래프는 정점 집합 V와 간선 집합 E로 G = (V, E)와 같이 나타낸다.

주요 메서드

메서드	설명	시간복잡도
addVertex(T v)	정점 추가 (이미 있으면 무시)	O(1)
addEdge(T u, T v)	두 정점을 잇는 간선 추가	O(1)
getNeighbors(T u)	u에 인접한 정점 목록 반환	O(1)
degree(T u)	차수 (무방향 기준, 방향이면 진출 차수)	O(1)
isAdjacent(T u, T v)	두 정점이 인접한지 확인	O(차수)
print()	그래프 전체 출력	O(V + E)

그래프 표현 방식

그래프를 저장하는 방법은 크게 두 가지다.

1. 인접 행렬 (Adjacency Matrix)

2차원 배열 matrix[i][j]로 표현한다. i와 j가 연결돼 있으면 1, 아니면 0.

• 두 정점의 연결 여부를 O(1)로 확인
• 항상 O(V²) 공간을 사용 → 간선이 적은 희소 그래프에서는 낭비가 크다

2. 인접 리스트 (Adjacency List) — 본 구현 방식

각 정점마다 연결된 정점들의 목록을 저장한다.

• 공간 효율이 좋다 O(V + E)
• 두 정점의 연결 여부 확인은 O(차수)
• 실무와 문제 풀이에서 가장 많이 쓰인다

왜 Map을 사용하는가

정점을 0 ~ n-1 정수로 고정하면 List<List<Integer>>나 배열로도 구현할 수 있다. 하지만 정점이 문자열("A")이거나 값이 띄엄띄엄한 경우 배열 인덱스로는 다루기 어렵다.

Map<T, List<T>>를 사용하면 정점을 어떤 타입(문자열, 정수, 객체)이든 key로 쓸 수 있어 제네릭 그래프를 유연하게 구현할 수 있다.

방향 그래프 vs 무방향 그래프

directed 플래그로 구분한다.

• 무방향(Undirected) : 간선이 양방향. (u, v)와 (v, u)가 같다 → 양쪽 목록에 모두 추가
• 방향(Directed) : 간선이 단방향. u -> v만 추가