간선을 한 번 넣을지 두 번 넣을지
무방향 기본값을 남발하면 방향 그래프 반례에서 바로 틀립니다.
간선을 저장하기 전에 입력 조건을 확정한다
방향성, 가중치, 다중 간선, 정점 번호 기준을 먼저 정하면 인접 리스트와 행렬 선택도 같은 기준으로 설명됩니다.
존재 여부와 비용을 분리
가중치 타입과 범위는 BFS, 다익스트라 선택까지 이어집니다.
다중 간선 정책을 명시
허용, 최소 가중치 병합, 카운트 보존 중 하나로 고정합니다.
0-based와 1-based를 통일
파싱 직후 정규화하면 탐색 코드의 인덱스 오류가 줄어듭니다.
희소 그래프
이웃 순회가 많으면
인접 리스트가 공간과 순회
비용에서 유리합니다.
밀집 그래프
간선 존재 질의가 매우 잦으면 행렬의 O(1) 조회를 검토합니다.
성장 위험
정점 수가 커지면 행렬 공간은
V^2로 빠르게
커집니다.