인접 리스트 질의
1의 이웃: [2, 3]`has_edge(1,3)`은 리스트 안에서 3을 찾습니다.
O(deg(1))이웃 수가 많으면 질의 비용도 커집니다.
O(V+E)대신 저장 공간은 실제 간선만큼만 씁니다.
리스트는 이웃을 훑고, 행렬은 칸 하나를 바로 읽는다
같은 간선 집합이라도 주 연산이 이웃 순회인지 존재 조회인지에 따라 표현 선택이 달라집니다.
인접 행렬 질의
0
1
2
3
0
0
1
0
0
1
0
0
1
1
2
0
0
0
1
O(1)`matrix[1][3]` 칸 하나로 확인합니다.
O(V²)정점 수가 크면 빈 칸까지 모두 저장합니다.
판정: 존재 질의가 매우 많고 V가 작거나 밀집 그래프면 행렬, 탐색과 순회 중심이면 리스트가 보통 더 낫습니다.