프로그래밍에서는 그래프를 나타낼 수 있는 방법이 크게 2가지 존재한다.
- 인접행렬(adjacency matrix)
- 2차원 배열로 그래프의 연결관계를 나타낸 것
- 연결된 노드는 1, 연결되지 않은 노드는 0으로 표기할 수 있다.
- 연결되지 않은 노드를 python에서 표기할 때 무한의 비용(999999999)로도 표기할 수 있다.
-> 아래의 코드에 0에는 무한의 비용을 넣을 수도 있다.
graph = [
# 1 2 3
[0, 1, 1], # 1
[1, 0, 0], # 2
[1, 0, 0] # 3
]
- 인접리스트(adjacency list)
- 리스트로 그래프의 연결을 나타내는 방식
- 각 노드의 연결된 노드를 리스트로 나타낸다.
인접행렬 vs 인접리스트
- 인접행렬은 노드별로 연결되어 있는지 파악하기가 인접리스트에 비해 편하다. 그러나 데이터가 많아 진다면 차지하는 공간도 많아지기에 공간복잡도 측면으로는 인접리스트가 더 좋다고 볼 수 있다.
- 인접리스트는 특정 노드와 연결되어 있는지를 확인하기 위해서는 그 노드를 순회해야 한다.
👋🏻