[그래프(Graph)]
그래프(graph)란 노드(node)와 노드 사이에 연결된 간선(edge)의 정보를 가지고 있는 자료구조를 의미한다. 알고리즘 문제를 접했을 때 '서로 다른 개체(혹은 객체)가 연결되어 있다.'는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 한다. 예를 들어 '여러 개의 도시가 연결되어 있다'와 같은 내용이 등장하면 그래프 알고리즘을 의심해보자.
그래프 자료구조 중에서 트리(Tree) 자료구조는 다양한 알고리즘에서 사용되므로 꼭 기억하자. 트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델에 속한다.
[그래프의 구현 방법]
- 인접 행렬 : 2차원 배열을 사용하는 방식
- 인접 리스트 : 리스트를 사용하는 방식
인접 행렬을 이용하는 방식은 간선 정보를 저장하기 위해서 O(V^2)만큼의 메모리 공간이 필요하다. 반면에 인접 리스트를 이용할 때는 간선의 개수만큼인 O(E)만큼만 메모리 공간이 필요하다.
또한 인접 행렬은 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1)의 시간으로 즉시 알 수 있다는 장점이 있으며, 반면에 인접 리스트를 이용할 때는 O(V)만큼의 시간이 소요된다.
- 다익스트라 최단 경로 알고리즘은 인접 리스트 방식
- 플로이드 워셜 알고리즘은 인접 행렬을 이용하는 방식 (2차원 리스트 생성)
