그래프

그래프

그래프는 노드(node)와 간선(edge)로 표현되며 이때 노드를 정점(vertex)이라고도 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다.

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

• 인접 행렬(Adjacent Matrix)
• 인접 리스트(Adjacent Lint)

인접 행렬

2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 파이썬에서는 리스트를 사용한다. 연결되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다.

 

인접 행렬 방식 예제

INF=999999999 # 무한의 비용 선언

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

 

인접 리스트

각 노드에 대해 인접한 노드를 차례대로 연결하여 저장한다. C++나 자바와 같은 프로그래밍 언어에서는 별도의 연결 리스트 기능을 위한 표준 라이브러리를 사용한다. 반면에 파이썬은 리스트 자료형이 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))

 

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

메모리 측면에서 보자면 인접 행렬 방식은 인접 리스트 방식에 비해 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.

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