인접 행렬과 인접 리스트

그림 출처 : https://sarah950716.tistory.com/12

• 인접 행렬 예시
  

• 인접 리스트 예시
  

* 동빈북 참고

인접 행렬

INF = int(1e9)

graph = list()
x0 = [0, 7, 5]
x1 = [7, 0, INF]
x2 = [5, INF, 0]

graph.append(x0)
graph.append(x1)
graph.append(x2)

for k in graph:
    print(k)

• 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다.
• 구현이 쉽다.
• 두 노드 간의 연결 관계를 확인하고 싶을 때 단지 인덱스로 접근하여 0인지, 1인지 확인하면 되기 때문에 O(1)이라는 시간 복잡도로 빠르게 확인할 수 있다.
• 모든 관계(연결되지 않은 것까지)를 저장하므로, 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.

인접 리스트

graph = [[] for _ in range(3)]

graph[0].append((1, 7))
graph[0].append((2, 5))

graph[1].append((0, 7))

graph[2].append((0, 5))

for k in graph:
    print(k)

• 연결된 정보만 (연결되지 않은 것은 제외) 저장하기에 메모리 낭비가 적다.
• 두 노드 간의 연결 관계를 확인하고 싶을 때는 탐색이 필요하기에 속도가 느리다.