[자료구조] 그래프 표현 3가지 방법 (인접 행렬, 인접 리스트, 간선 리스트)

그래프는 정점(또는 노드)와 간선(또는 링크)들로 이루러진 자료구조를 말한다. 

그래프의 표현 방법에는 3가지가 있다.

1. 인접 행렬(Adjacency matrix)

2. 인접 리스트(Adjacency list)

3. 간선 리스트(Edge list)

 

위 3가지 방법에 대해 정리하고자 한다.

 

 

인접 행렬(Adjacency matrix)

• 노드를 중심으로 그래프 표현하며, 2차원 배열을 자료 구조로 이용한다.
• 노드의 수가 n이라면 nxn 형태의 2차원 배열이 인접 행렬로 사용된다.
• 인접 행렬에서 행, 열은 노드를 의미하고, 값은 에지를 의미한다.
  • 가중치 없는 그래프에서는 에지가 있다면 1을 보통 저장한다.
  • 가중치 있는 그래프에서는 에지가 있을 때, 가중치를 저장한다. (이때, 가중치가 0인 것과 에지가 없는 경우 구분이 되야 함)
  • 무방향 그래프에서는 대칭적인 구조를 가진다. 1번과 2번 노드가 연결되어있다면 A[1][2]=1, A[2][1]=1이 된다.
• 장점
  • 두 노드를 연결하는 에지나 가중치 값을 조회할 때, 시간복잡도는 O(1)이 된다. (배열에 접근시 바로 확인가능)
  • 구현이 쉬운 편이다. 
• 단점
  • 한 노드와 연결된 에지를 모두 확인하려면 n번 봐야한다. (시간복잡도 O(n))
  • 노드 개수에 비해 에지가 적다면 메모리 공간이 낭비된다. (노드의 수가 n이라면 nxn 배열 필요) 
  • 노드의 개수가 너무 많다면 2차원 배열로 아예 만들 수가 없다.
    • 노드 개수가 3만개를 넘으면 자바에서는 자바 힙 스페이스 에러 발생

 

 

인접 리스트(Adjacency list)

• 노드를 중심으로 그래프 표현하며, ArrayList를 노드 개수만큼 선언해 사용한다.
• 노드가 n개라면 n개의 인접리스트가 존재하며, 각 노드와 인접한 노드를 각각 리스트로 만들어서 표현한다.
• 
  
  • 가중치 없는 그래프에서는 1번 노드와 2,3번 노드가 연결되어 있다면 (자료형은 Integer형) ArrayList[1][0]=2, ArrayList[1][1]=3이 된다.
  • 가중치 있는 그래프에서는 노드번호 1과 2는 가중치 1로, 1과 3은 가중치 8로 연결되어 있다면 (자료형을 Node 클래스로) ArrayList[1]에 [ (2,1), (3,8) ]이 저장된다.
  • 무방향 그래프에서는 1번과 2번 노드가 연결되어있다면  ArrayList[1][0]=2, ArrayList[2][0]=1이 된다.
• 장점
  • 연결된 노드의 정보만 저장하기 때문에, 한 노드와 연결된 에지들을 찾는 시간이 매우 빠르다. (각 리스트에 담긴 원소만 확인하면 된다.)
    • 모든 리스트의 원소의 수가 에지의 수와 같다.
  • 각 노드에 연결된 노드를 모두 방문을 할 경우, 보다 빠르게 방문할 수 있다.
  • 노드 개수가 많아져도 공간 효율이 좋기 때문에, 이로 인한 에러가 발생하지 않는다.
• 단점
  • 두 노드를 연결하는 에지나 가중치 값을 조회할 때, 리스트를 돌며 확인해야 하기 때문에, 시간복잡도는 O(V)이 된다. (V는 정점(노드)의 수를 의미)
  • 구현이 복잡한 편이다.

 

노드 개수에 비해 에지 개수가 훨씬 적거나 각 노드에 연결된 모든 노드를 방문해야 한다면 인접리스트가 더 효율적이고, 두 노드의 연결관계만 확인한다면 인접행렬이 더 효율적이다. 

 

 

 

간선 리스트(Edge list)

• 에지를 중심으로 그래프를 표현하며, 2차원 배열을 사용한다.
• 간선의 개수만큼의 배열의 열이 필요하고, 행은 출발 노드와 도착 노드 또는 출발 노드, 도착 노드, 가중치를 저장하기 위해 2개 또는 3개가 필요하다.
  • 가중치 없는 그래프에서는 출발 노드와 도착 노드의 저장을 위해 간선의 개수를 E라 할 때, 2xE 크기의 배열이 필요하다. 1번 노드와 2,3번이 연결되어 있다면 E[0][0]=1, E[0][1]=2로, E[1][0]=1, E[1][1]=3으로 저장된다.
  • 가중치 있는 그래프에서는 출발 노드, 도착 노드, 가중치의 저장을 위해 간선의 개수를 E라 할 때, 3xE 크기의 배열이 필요하다. 
  • 무방향 그래프에서는 1번과 2번 노드가 연결되어있다면 [1,2], [2,1]로 표현해 배열에 저장한다.
• 구현이 비교적 쉬운 편이고 벨만 포드나 크루스칼 알고리즘에서 사용한다.