그래프는 노드와 에지로 구성된 집합이다.

1. 에지 리스트 : 에지를 중심으로 그래프를 표현

• 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다.
• 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.
• 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다.
• 에지 리스트는 벨만 포드나 크루스칼(MST 알고리즘)에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다.

1. 인접 행렬 : 2차원 배열을 자료구조로 이용하여 그래프를 표현한다.

• 인접 행렬은 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다.
• 두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있는 것이 장점이다.
• 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
• 노드 개수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없는 결함이 있다.
• 노드가 3만 개가 넘으면 자비 힙 스페이스 에러가 발생한다.

1. 인접 리스트 : ArrayList로 그래프를 표현한다. 노드 개수만큼 ArrayList를 선언한다.

• 노드와 연결되어있는 에지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다.
• 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.