그래프(Graph)
그래프란?
그래프는 노드와 엣지로 구성된 집합이다.
| 구성 요소 | 설명 |
|---|---|
| 노드(Vertices) | 그래프에서 데이터를 표현하는 단위 |
| 에지(Edge) | 노드와 노드의 연결 관계를 나타내는 선 |
트리 또한 그래프의 일종이다.
그래프의 표현
엣지 리스트
엣지 리스트는 엣지를 중심으로 그래프를 표현한다.
엣지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 엣지를 표현하거나
출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 엣지를 표현한다
엣지 리스트로 가중치가 없는 그래프 표현
가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하기 때문에 배열의 행은 2개면 충분하다.
위 사진은 방향이 있는 그래프의 예이며, 만약 방향이 없는 그래프라면 [1,2], [2,1]은 같은 표현이다.
엣지 리스트로 가중치가 있는 그래프 표현
가중치가 있는 그래프는 행을 3개로 늘려 3번째 행에 가중치를 저장한다.
엣지 리스트는 특정 노드와 관련되어 있는 엣지를 탐색하기는 어렵다.
엣지 리스트는 벨만 포드나 MST 알고리즘에 사용하며, 노드 중심 알고리즘에서는 잘 사용하지 않는다.
인접 행렬
인접 행렬로 가중치가 없는 그래프 표현
상기 사진은 노드가 5개인 그래프를 5 x 5 안접 행렬로 표현한 것이며 1에서 2를 향하는 엣지를 인접 행렬은 1행 2열에 1을 저장하는 방식으로 표현한다. 1을 저장하는 이유는 가중치가 없기 때문
인접 행렬은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다.
인접 행렬은 노드 중심으로 그래프를 표현한다.
인접 행렬로 가중치가 있는 그래프 표현
2에서 5로 향하는 엣지의 가중치(15)를 2행 5열에 기록한다.
인접 행렬을 이용한 그래프의 장점
- 두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있다.
인접 행렬을 이용한 그래프의 단점
- 노드와 관련되어있는 엣지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 엣지가 적을 때는 공간 효율성이 떨어진다.
- 노드 개수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없다.(자바의 경우 노드가 3만개가 넘으면 자바 힙 스페이스 에러 발생)
위와 같은 장단점을 고려하여 인접 행렬은 노드의 개수에 따라 사용 여부를 적절하게 판단하고 사용해야한다.
인접 리스트
인접 리스트는 제일 많이 사용하는 그래프 표현의 방식으로 ArrayList로 그래프를 표현한다. 노드 개수만큼 ArrayList를 선언한다.
인접 리스트로 가중치가 없는 그래프 표현
인접 리스트에는 N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현한다.
상기 사진은 방향이 있는 그래프를 표현한 것이며, 노드 1과 연결된 2, 3 노드는 ArrayList[1]에 [2,3]을 연결하는 방식으로 표현한다
인접 리스트로 가중치가 없는 그래프 표현
가중치가 없는 경우는 Integer등과 같은 자료형을 사용했지만, 가중치가 있는 경우는 Node와 같은 클래스를 선언(클래스 필드로는 예를 들어 도착 노드, 가중치)하여 ArrayList에 사용한다.
상기 사진을 보면 ArrayList[1]에 [(2,8), (3,3)]이 연결되어 있는데 이는 시작 노드 1과 도착 노드 2가 가중치 8 엣지로, 시작 노드 1과 도착 노드 3이 가중치 3 엣지로 연결되어 있다는 것을 보여준다.
그래프를 표현하는 다른 방법(엣지 리스트, 인접 행렬)에 비해 그래프 구현은 복잡한 편이나. 노드와 연결되어 있는 엣지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋다.(리스트를 사용하기 때문에 가변적)
