[Algorithm] 그래프(Graph)

1. 그래프(Graph)란?

정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조

(1) 간선(Edge) 종류

• 무방향

• 방향

• 가중치

(2) 정점의 차수(Degree)

정점 x에 연결된 간선의 수

deg(x) := 정점 x의 차수(degree)

(3) 차수의 성질

모든 정점의 차수의 합 = 간선의 개수의 2배

 

2. 그래프(Graph)를 저장하는 방법

(1) 인접 행렬 (Adjacency Matrix)

• int[][] adj = int new[V][V]
• O(V^2) 만큼의 공간 필요
• A에서 B로 이동 가능? 가중치 얼마? => O(1)
• 정점 A에서 갈 수 있는 정점들은? => O(V)
• ex) V=10만, E=50만 => V^2 = 100억 = 10GB 

 

 

(2) 인접 리스트 (Adjacency List)

• ArrayList <Integer>[] adj
• O(E) 만큼의 공간 필요
• A에서 B로 이동 가능? 가중치 얼마? => O(min(deg(A), deg(B)))
• 정점 A에서 갈 수 있는 정점들은? => O(deg(A))
• ex) V=10만, E=50만 => 5*10^5 = 500K

 

 

 

 

 

(3) 요약

• A와 B를 잇는 간선 존재 여부 확인을 물어보는 문제 => 인접 행렬
• A와 연결된 모든 정점 확인 => 인접 리스트 
• But 간선의 수가 많아서 공간 복잡도의 제한을 넘어간다면 인접 리스트를 사용해야 한다.

 

3. 그래프(Graph) 문제의 핵심

• 정점(Vertex) & 간선(Edge)에 대한 정확한 정의
• 간선 저장 방식을 확인하기 => 대부분 인접 리스트를 사용하는 것이 좋다.