그래프(Graph)란?
그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다.
vertex : 정점
edge : 정점과 정점을 연결하는 간선
아래는 대표적인 그래프 종류들의 예시다.
그래프 구현 - 인접 행렬
행렬로 구현하는 방식
정점 a와 정점 b를 잇는 간선이 있을 경우, 행렬(a,b)에 1을 표기해준다.
만약 가중치가 있는 그래프라면 1 대신 가중치를 넣을 수 있다.
기본적으로 무방향 그래프의 경우는 (a,b) (b,a)에 모두 간선 값을 넣지만, 방향 그래프같은 경우는 위의 표와 같이 방향에 맞는 간선만 표기한다.
그래프 구현 - 인접 리스트
리스트로 구현하는 방식
해당 노드와 연결되어있는 노드들을 리스트로 쭉 붙이는 방식이다.
ArrayList를 사용하여 코드로 구현한다.
인접 행렬과 인접 리스트의 장단점
| 인접 행렬 | 인접 리스트 | |
|---|---|---|
| 시간 복잡도 | O(N^2) 정점 N * N만큼 필요 | O(N) N : 간선의 개수 |
| 두 정점의 연결 여부 | graph[x][y] 의 값으로 한번에 확인 | graph 의 원소에서 y가 나올때까지 탐색 |
| 인접 노드 파악 여부 | N * N만큼 반복문을 돌아 확인한다. | 각 리스트에 담겨있는 원소를 확인한다. |
행렬의 경우
- 두 정점이 연결되있는지를 확인하는 방법이 쉽다.
- graph[x][y]의 값을 바로 확인해서 유무를 판단할 수 있기 때문이다.
- 단, 정점이 N개인 경우, 행렬을 만들기 위해선 N * N만큼의 공간이 필요하게 된다.
무방향 그래프의 경우는 절반의 공간이 낭비되는 셈이다.
리스트의 경우
- 실제 연결된 노드들만 리스트 원소에 담겨있으므로 공간 복잡도가 N(간선)이다.
- 다만, 두 정점 x, y가 연결되있는지 알고 싶다면 노드x 리스트로 들어가 원소 y가 있는지 처음부터 쭉 탐색해야 하므로 행렬보다 더 많은 시간이 소요된다.
간선이 많은 그래프의 경우, 인접 행렬을 통해 빠르게 연결 여부를 확인할 수 있다.
반면 간선이 적은 그래프의 경우는 인접 리스트를 통해 인접 노드를 빠르게 확인할 수 있다.
참고
https://born2bedeveloper.tistory.com/42
