정점은 많지만 연결은 적은 그래프를 저장하려 합니다. 인접 행렬과 인접 리스트 중 무엇을 선택하나요?

정점은 많고 실제 연결이 적은 희소 그래프라면 인접 리스트를 우선 검토하겠습니다. 각 정점에 실제 이웃의 목록만 저장하므로 공간이 정점 수의 제곱이 아니라 정점 수와 간선 수에 비례하기 때문입니다. 다만 두 정점의 연결 여부를 매우 자주 확인하거나 그래프가 조밀하다면 인접 행렬의 단순한 주소 계산과 좋은 지역성이 더 유리할 수 있어, 희소도만으로 결정하지 않겠습니다.

밀도와 갱신 비용을 함께 봅니다

인접 행렬은 adj[u][v]처럼 두 정점의 관계를 바로 확인할 수 있고 가중치도 같은 위치에 저장하기 쉽습니다. 대신 정점이 V개이면 연결이 없어도 V×V 공간을 예약합니다. 인접 리스트는 u의 실제 이웃만 순회하므로 BFS나 DFS처럼 모든 이웃을 보는 작업에 자연스럽지만, 특정 v가 목록에 있는지 찾으려면 차수만큼 검사해야 합니다. 리스트 안을 정렬하거나 해시 집합을 추가하면 존재 조회는 빨라질 수 있지만 갱신·메모리 비용이 늘어납니다. 이를 희소 그래프 표현(sparse graph representation)과 조밀 그래프 표현(dense graph representation)의 선택 문제로 정리할 수 있습니다.

방향 그래프에서는 나가는 간선과 들어오는 간선 조회가 다릅니다. 작업이 역방향 탐색이나 진입 차수 계산이라면 역방향 리스트를 함께 보관할지 결정합니다. 무방향 그래프는 한 간선을 양쪽 리스트에 저장하는 방식이 순회에는 편하지만 저장량이 두 배가 됩니다. 비용 0인 간선과 간선 없음도 같은 값으로 표현하면 최단 경로 결과가 틀릴 수 있으므로 별도 상태나 무한대 값을 사용하겠습니다.

알고리즘과 갱신을 함께 맞춥니다

경로 탐색이 주된 작업이면 리스트가 읽는 간선을 실제 간선 수로 제한해 유리합니다. 행렬은 밀집 그래프나 SIMD·비트 연산을 활용하는 작은 정점 집합에서 경쟁력이 있습니다. 그래프가 거의 정적이고 메모리 접근 속도가 중요하면 CSR처럼 행의 시작 위치와 간선 배열을 분리한 압축 표현도 선택할 수 있지만, 중간 삽입과 삭제는 불리해집니다.

테스트는 고립 정점, 자기 간선, 중복 간선, 방향성, 0 비용을 포함하고 표현을 바꿔도 동일한 그래프 의미가 보존되는지 확인하겠습니다. 실제로는 V와 E만 보지 않고 간선 갱신률, 이웃 순회 비율, 캐시 효율, 메모리 상한을 측정합니다. 인접 리스트가 희소 그래프에서 흔히 적합하다는 결론과 어떤 질의에도 항상 최선이라는 주장은 다릅니다.

인접 행렬은 u, v 위치를 바로 읽어 연결 여부를 확인할 수 있지만 V² 칸을 유지합니다. 인접 리스트는 실제 E개 간선만 저장해 희소 그래프에서 유리하고 BFS·DFS처럼 이웃을 순회할 때 검사량이 E에 가깝습니다. 다만 리스트에서 특정 간선을 찾는 비용은 차수에 비례하고, 해시 집합을 덧붙이면 메모리와 갱신 비용이 늘어납니다.

그래프가 거의 정적이면 CSR처럼 이웃을 연속 배열에 모아 리스트의 공간 효율과 행렬에 가까운 순회 지역성을 얻을 수 있지만 삽입·삭제가 어렵습니다. 방향 그래프의 들어오는 간선과 나가는 간선을 모두 자주 보면 역방향 구조를 별도로 둘지 결정합니다. 0 비용 간선과 간선 없음, 중복 간선의 의미를 고정하고 같은 간선 집합을 세 표현으로 변환한 결과가 일치하는지 검증하겠습니다.

무방향 그래프를 인접 리스트로 만들면 간선 하나를 양 끝의 목록에 저장해 총 항목 수는 보통 2E가 됩니다. 방향 그래프의 진입 차수를 자주 바꾸거나 역방향 탐색이 필요하면 역간선 목록도 유지합니다. 같은 두 정점 사이 여러 비용의 간선이 있을 때 행렬 한 칸에 최솟값만 남기면 다중 간선의 개수와 정체성을 잃으므로 입력 의미를 먼저 고정하겠습니다.