인접 행렬 인접 리스트

그래프를 구현하는 방법으로 인접 행렬과 인접 리스트의 방법이 있다.

인접 행렬

인접 행렬 (Adjacency Materix)

- 그래프의 정점을 2차원 배열로 만드는 것

- 정점(노드)의 개수가 n 개라면 n * n 형태의 2차원 배열 사용

- 무방향 그래프는 인접행렬이 대칭적 구조

- 가중치 그래프 경우 행렬에 간선(링크)의 가중치 값 저장

- 그래프에 간선(링크)이 많이 존재하는 밀집 그래프의 경우 사용

장점

- 구현이 비교적 간단하다.

- 두 정점(노드)을 연결하는 간선(링크)을 조회할 때 0(1) 시간복잡도를 가진다.

- 정점(노드) (i)의 차수를 구할 때 인접행렬의 (i)번째 행의 값을 모두 더하여 0(n) 시간복잡도를 가진다.

 

단점

- 간선(링크)의 수와 무관하게 n² 크기의 2차원 배열이 필요하여 메모리 낭비가 크다.

- 그래프의 모든 간선(링크)를 알아내기 위해 인접행렬 전체를 확인하여 O(n²)의 시간복잡도를 가진다. 

  (노드의 갯수가 100개이고 링크가 1개일 때 1개의 연결을 찾기위해 100개의 노드를 확인해야한다.)

인접 리스트

인접 리스트 (Adjacency List)

- 실제로 연결된 노드들에 대한 정보만 저장

- 간선(링크)의 갯수에 비례하는 메모리만 차지

- 그래프의 정점(노드)에 인접한 정점(노드)들을 연결리스트로 만드는 것 

- 정점(노드)의 개수만큼 인접리스트가 존재하며 각각의 인접리스트에 인접한 정점(노드) 정보 저장

- 그래프는 각 인접리스트에 대한 헤드포인터를 배열로 갖는다.

- 그래프 내에 적은 숫자의 간선(링크)를 가지고 있는 희소 그래프의 경우 사용

장점

- 존재하는 간선(링크)의 수만 관리하여 메모리를 효율적으로 사용

- 그래프의 모든 간선(링크)를 알아내기 위해 각각의 모든 인접리스트를 탐색하여 O(n + e)의 시간복잡도를 가진다.

 

단점

- 구현이 비교적 어렵다.

- 두 정점(노드)가 연결 되었는지 확인 할 때 인접행렬 보다 비효율 적이다.

  (두 노드의 연결을 확인하기 위해 하나의 노드의 리스트 전체를 돌며 확인해야 한다.)