그래프를 구현하는 3가지 방법에 대해 알아보았다.
에지 리스트
에지 리스트(edge list)는 에지를 중심으로 그래프를 표현한다.
에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다.
또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.
가중치 없는 에지 리스트
1에서 2로 뻗어나가는 에지는 [1, 2]로 표현한다. 4에서 5로 뻗어나가는 에지는 [4, 5]로 표현한다.
이처럼 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다.
그리고 노드를 배열에 저정하여 에지를 표현하므로 에지 리스트라고 한다.
가중치 있는 에지 리스트
가중치가 있는 그래프는 행을 3개로 늘려 3번째 행에 가중치를 저장하면 된다.
1에서 2로 향하는 가중치가 8인 에지는 [1, 2, 8]로 표현한다.
이처럼 에지 리스트는 구현하기 쉽다. 하지만 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않아 노드 중심 알고리즘에는 잘 사용하지 않는다.
인접 행렬
인접 행렬(adjacency matrix)은 2차원 배열을 자료 구조로 이용하며 그래프를 표현한다.
인접 행렬은 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다..
가중치 없는 인접 행렬 그래프
1에서 2를 향하는 에지를 인접 행렬은 1행 2열에 1을 저장하는 방식으로 표현한다.
가중치 있는 인접 행렬 그래프
가중치가 있는 그래프는 1 대신에 가중치를 저장한다.
인접 행렬을 이용한 그래프는 구현이 쉽고, 두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있는 장점이 있다.
하지만 노드와 관련되어있는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
또한 노드 개수가 많은 경우 2차원 배열 선언 자체를 할 수 없는 결함도 있다.
인접 리스트
인접 리스트(adjacency list)는 ArrayList로 그래프를 표현한다. 노드 개수만큼 ArrayList를 선언하고 자료형은 경우에 맞게 사용한다.
가중치 없는 인접 리스트 그래프
인접 리스트는 N번 노드와 연결되어 있는 노드의 배열 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현한다.
예를 들어 노드 1과 연결된 2, 3 노드는 ArrayList[1]에 [1, 3]을 연결하는 방식으로 표현한다.
가중치 있는 인접 리스트 그래프
가중치가 있을 경우, 노드 1의 경우 ArrayList[1]에 [(2, 8), (3, 3)]을 연결하는 방식으로 표현한다.
인접 리스트를 이용한 그래프 구현은 다른 방법에 비해 복잡하다.
하지만 노드와 연결되어 있는 에지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다.
이런 장접으로 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.
- Do it! 알고리즘 코딩테스트 자바 편
