Graph
- 네트워크 모델
- 2개 이상의 경로가 가능하다. / 사이클이 존재할 수 있다.
- 방향 그래프와 무방향 그래프가 존재한다.
- 구현 방법: 인접 행렬, 인접 리스트
구현 방법
인접 행렬
- 간선의 수와 무관하게 N^2개의 메모리 공간이 필요 / 그래프에 존재하는 모든 간선의 수는 O(N^2)에 알 수 있다.
- 그래프에 간선이 많이 존재하는 Dense Graph에 효과적
- 인접한 노드를 찾기 위해서는 모든 노드를 순회해야하기 때문에
노드의 개수 < 간선의 개수
인접 리스트
- 그래프에 존재하는 모든 간선의 수는 O(N+E) 안에 알 수 있다.
- 그래프에 간선이 적게 존재하는 Sparse Graph에 효과적
노드의 개수 > 간선의 개수
참고
Positive Thinking