그래프 표현 - 인접 행렬과 인접 리스트

# 그래프 : 

                    0️⃣

                      |

1️⃣----7----ᅩ-----5----2️⃣

 

- 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

- 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식

 

# 인접행렬

	0	1	2
0	0	7	5
1	7	0	INF
2	5	INF	0

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

INF = 987654321

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

 

 

* 노드1과 노드7의 거리?

→ graph[1][7]

 

# 인접 리스트

0️⃣ --→ (1️⃣ ,  7) --→ (2️⃣ ,  5)

1️⃣ --→ (0️⃣ ,  7)

2️⃣ --→ (0️⃣ , 5)

 

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

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))

 

 

 

# 인접 행렬과 인접 리스트의 차이

	인접 행렬	인접 리스트
메모리 측면	모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비	연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용
두 특정 노드가 연결되어 있는지 정보를 얻는 속도	빠르다	느리다
노드1과 노드7의 거리?	graph[1][7]	노드1에 대한 인접리스트(graph[1])를 앞에서부터 차례대로 확인
특정한 노드와 연결된 모든 인접 노드를 순회할 경우		더 메모리 공간의 낭비가 적다