질문이 “연결되어 있나?”
두 정점 연결 여부를 자주 묻는 조밀 그래프라면 인접 행렬이 빠르다.
graph representation
그래프는 “저장 방식”과 “질문 유형”을 같이 고른다
같은 정점과 간선이라도 연결 확인, 전체 순회, 최단 경로, 최소 비용 연결 중 무엇을 묻는지에 따라 표현과 알고리즘이 달라진다.
행렬: 빠른 연결 확인
리스트: 이웃 순회
간선 리스트: 비용 정렬
가중치 그래프 예시
질문이 “이웃을 모두 방문하라”
간선이 적고 DFS/BFS를 반복하면 인접 리스트가 공간과 순회에 유리하다.
질문이 “가장 싼 연결을 고르라”
간선을 비용순으로 다루는 MST 문제는 간선 리스트가 자연스럽다.
표현 방식과 대표 문제 대응
| 문제 단서 | 먼저 고를 표현 | 이어지는 알고리즘 |
|---|---|---|
| 간선이 많고 연결 여부 확인 | 인접 행렬 | 행·열 값으로 즉시 확인 |
| 간선이 적고 전체 방문 | 인접 리스트 | DFS 또는 BFS |
| 무가중 최단 거리 | 인접 리스트 | BFS 레벨 탐색 |
| 최소 비용 신장 트리 | 간선 리스트 | Kruskal 또는 Prim 계열 |