전체 정점 개수: N
젠체 간선 개수: E
1. 인접 행렬
그래프의 연결 관계를 이차원 배열로 표현하는 방법이다.
graph라는 이차원 배열이 있다고 하자.
이에 인접 행렬을 다음과 같이 정의할 수 있다.
1) 가중치가 없을 때
graph[i][j]: 노드 i에서 노드 j로 가는 간선이 있다면 1, 없다면 0.
1) 가중치가 있을 때
graph[i][j]: 노드 i에서 노드 j로 가는 간선이 있다면 가중치, 없다면 INF.
장점
두 정점을 연결하는 간선을 조회할 때 시간복잡도가 O(1)이다.
단점
1. 간선 수에 상관없이 N^2크기의 이차원 배열이 필요하다. 메모리 낭비이다.
2. 모든 간선 수를 알아내기 위한 시간복잡도가 O(N^2)이다.
2. 인접 리스트
그래프의 각 정점에 인접한 정점들을 연결리스트로 표현하는 방법이다.
정점의 개수만큼 인접 리스트가 존재한다.
각 인접 리스트에는 인접한 정점의 정보가 저장된다.
장점
1. 존재하는 간선만을 저장한다. 인접 행렬에 비해 메모리 측면에서 효율적이다.
2. 모든 간선 수를 알아내기 위한 시간복잡도가 O(N + E)이다.
단점
두 정점을 연결하는 간선을 조회하거나, 정점에 연결된 간선의 수[차수]를 알기 위해서는
정점의 인접 리스트를 탐색해야 한다. 이 정보를 얻는 속도가 인접 행렬에 비해 느리다.