그래프(트리)를 코드로 나타내는 방법

1. 인접행렬

인접 행렬은 코드에 간선 정보를 담는 방식이며 코드로는 2차원 배열을 만든다.

i번 행의 j번 열은 i노드 → j노드를 잇는 간선을 의미한다.

• 무방향 그래프
  

무방향 그래프는 양방향 그래프와 같다. 무방향 그래프는 가운데 대각선을 기준으로 대칭의 형태를 가지고 있다.

a→b로 갈 수 있다면 b→a로도 갈 수 있기 때문이다.

• 방향 그래프
  

2. 인접 리스트

각 행이 간선의 시작노드를 의미하고 행마다 간선의 도착 노드를 저장하는 형태이다.

코드에서는 리스트의 형태로 값을 저장한다.

• 무방향 그래프
  

• 방향 그래프
  

언제? 어떤 방법으로?

생각해보자! 노드가 n개라면??

→ 인접 행렬은 n의 제곱개 공간을 할당한다.

→ 인접 리스트는 간선 개수만큼 공간을 차지 하지 때문에 최악의 경우 n의 제곱개 공간을 할당한다.

대부분 간선은 모두 차있지 않기 때문에 인접 리스트가 공간적인 측면에서 유리하다.
시간과 메모리는 반비례 관계이기 때문에 메모리를 많이 차지하면 시간이 빠르다.
a에서 b로 가는 노드를 찾기 위해서라면 인접 행렬은 Arr[a][b]값을 찾아보면 되기 때문에 시간복잡도는 O(1) 이다.그에 반해 인접 리스트는 Arr[A]에 있는 데이터를 탐색해야 하기 때문에 O(N)이다.

결과적으로 입력 범위를 보고 노드 대비 간선의 최대 개수가 적은 편이라면 인접 리스트를! 비슷하다면 인접 행렬을 쓰는 것이 좋다.