[Algorithm] Graph - 인접 행렬, 인접 리스트

그래프

• 그래프의 개념

  정점과 간선으로 이루어진 자료구조의 일종 G=(V,E)

• 그래프 탐색

  하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방분하는 것

  EX) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지

인접 행렬

인접 행렬

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

연결이 되어있지 않은 노드끼리는 무한의 비용.

INF = 99999999 #무한의 비용 선언

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

print(graph)

→ 결과

[[0,7,5],[7,0,99999999],[7,0,99999999]]

인접 리스트

#행이 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)

→ 결과

[[(1,7),(2,5)],[(0,7)],[(0,5)]]

두 방식의 차이

• 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리 낭비가 심함.

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

  하지만 이와같은 속성 때문에 인접 리스트 방식은
  인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림.
  인접 리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문.

  특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다.