1
2, 3
2
4
3
empty
4
empty
같은 간선도 리스트와 행렬에서는 완전히 다른 모양으로 저장된다
표현을 바꾸면 메모리와 질의 비용뿐 아니라 디버깅할 때 보는 자료의 모양도 달라집니다.
입력 간선
(1,2)(1,3)(2,4)
1
2
3
4
1
0
1
1
0
2
0
0
0
1
3
0
0
0
0
리스트: 저장은 작고 순회가 빠르지만 존재 질의는 이웃을 훑습니다.
행렬: 존재 질의는 빠르지만 빈 칸까지 모두 저장합니다.
핵심: 같은 데이터를 다른 형태로 저장하면 이후 알고리즘의 병목도 달라집니다.