그래프(인접행렬/인접리스트)

• 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다.

  1. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

  2. 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

 

1. 인접 행렬(Adjacency Matrix)방식

• 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다.

• 연결 되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다.

• 실제 코드에서 논리적으로 정답이 될 수 없는 큰 값 중에서 999999999, 987654321 등의 값으로 초기화하는 경우가 많은데, 이렇게 그래프를 인접 행렬 방식으로 처리할 때는 다음과 같이 데이터를 초기화한다.

# 인접 행렬 방식
INF = 999999999 # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
  [0, 7, 5],
  [7, 0, INF],
  [5, INF, 0]
]

print(graph)

 

2. 인접 리스트(Adjacency List)방식

• 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

• 기본 자료형인 리스트 자료형이 append()와 메소드를 제공한다.

• 파이썬으로 인접 리스트를 이용해 그래프를 구현하고자 할 때에는 단순히 2차원 리스트를 이용하면 된다는 점만 기억하자 !!

# 인접 리스트 방식
# 행이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))

# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0,7))

# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0,5))

print(graph)

 

3. 두 방식은 어떤 차이가 있을까?

• 메모리 측면

  • 인접 행렬 방식 : 모든 관계를 저장하므로, 노드 개수가 많을수록 메모리가 불필요하게 낭비

  • 인접 리스트 방식 : 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용

 

• 속도 측면

  • 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 

  • 인접 리스트 방식에서는 연결된 데이터를 하나하나 확인해야 하기 때문이다.

 

이 글은 "이것이 코딩 테스트다" 에서 배운 내용을 정리하여 작성하였습니다.