에지 리스트는 에지를 중심으로 그래프를 표현한다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장해 에지를 표현한다. 또는 출발 노드, 도착 노드, 가중치를 저장해 가중치가 있는 에지를 표현한다.
가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다. 노드는 여러 가죠형을 사용할 수 있으며 다음의 경우 노드는 Integer형이다.
1에서 2로 뻗어나가는 에지는 [1, 2]로 표현한다. 4에서 5로 뻗어나가는 에지는 [4, 5]로 표현한다. 이처럼 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다. 그리고 노드를 배열에 저장해 에지를 표현하므로 에지 리스트라고 한다.
방향이 있는 그래프를 예로 들었는데, 방향이 없는 그래프라면 [1,2]와 [2,1]은 같은 표현
가중치가 있는 그래프는 행을 3개로 늘려 3번째 행에 가중치를 저장하면 된다.
1에서 2로 향하는 가중치가 8인 에지는 [1, 2, 8]로 표현한다. 에지 리스트는 구현하기 쉬운데, 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않다. 에지 리스트는 벨만 포드나 크루스칼(MST) 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다.
인접 행렬은 2차원 배열을 자료구조로 이용해 그래프를 표현한다. 인접 행렬은 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다.
1에서 2를 향하는 에지를 인접 행렬은 1행 2열에 1을 저장하는 방식으로 표현한다. 1을 저장하는 이유는 가중치가 없기 때문이다. 1에서 2로 향하는 에지가 있다는 표시를 노드 중심으로 한다고 이해하면 된다.
2차원 배열의 값에 가중치를 입력하면 됨.
