Graph를 표현하는 인접 행렬과 인접 리스트의 차이를 설명해주세요.

Graph는 정점(Vertex)과 간선(Edge)으로 관계를 표현하며, 대표 저장 방식으로 인접 행렬과 인접 리스트가 있습니다. 어떤 방식을 선택하느냐에 따라 메모리 사용량과 간선 조회/순회 성능이 달라집니다.

핵심 개념

• 인접 행렬은 V×V 2차원 배열로 간선 존재 여부를 O(1)에 확인합니다.
• 인접 리스트는 각 정점마다 연결된 정점 목록을 저장해 희소 그래프에서 메모리를 절약합니다.
• 밀집 그래프에는 행렬, 대부분의 실무/알고리즘 그래프에는 리스트가 자주 쓰입니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

정점: A, B, C
간선: A-B, A-C

인접 행렬
    A B C
A [0 1 1]
B [1 0 0]
C [1 0 0]

인접 리스트
A: B, C
B: A
C: A

const graph = new Map();
graph.set('A', ['B', 'C']);
graph.set('B', ['A']);
graph.set('C', ['A']);

실무에서 주의할 점

• 인접 행렬은 정점 수가 커지면 간선이 적어도 O(V²) 메모리를 사용합니다.
• 인접 리스트에서 특정 간선 존재 여부를 자주 확인하면 리스트 탐색 비용이 발생하므로 Set을 사용할 수 있습니다.
• 방향/무방향, 가중치 유무에 따라 저장 구조를 명확히 해야 합니다.

실무 적용 가이드

• BFS/DFS처럼 이웃 순회가 많으면 인접 리스트가 자연스럽습니다.
• 플로이드-워셜처럼 모든 쌍 관계를 다루는 알고리즘은 행렬이 편합니다.
• 대규모 그래프는 DB/그래프 엔진/압축 표현까지 고려합니다.

함께 연결해서 보면 좋은 키워드

Graph, Adjacency Matrix, Adjacency List, BFS, DFS

정리

Graph는 정점(Vertex)과 간선(Edge)으로 관계를 표현하며, 대표 저장 방식으로 인접 행렬과 인접 리스트가 있습니다입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.