그래프 개념

G = (V,E)

G = graph, V = vertex(점),    E = edge(선)

그래프란?

- 정점과 간선으로 이루어진 자료 구조

 

그래프의 표현법

1. G의 인접행렬

 

출처 : IOI KOREA : https://www.youtube.com/watch?v=LFMrrTqqt4M&t=966s

- 메모리 사용량 O(V^2)

- 한정점에 연결된 간선을 모두 순회할 때, 항상 O(V)의 사간을 사용

- 정점에 비해 간선이 몇 개 없는 그래프에서 비효율적으로 작동

- 메모리 사용량이 많음, 작은 메모리의 유리

 

2. 인접리스트

출처 : IOI KOREA : https://www.youtube.com/watch?v=LFMrrTqqt4M&t=966s

- 메모리 사용량 O(V+E)

- 메모리 사용량이 적으며, 희소 그래프를 표현하는 데 유리

- 한 정점에서 시작하는 간선을 모두 순회할 때, 연결된 정점의 개수만큼의 시간을 소요