그래프를 컴퓨터에서 표현하는 방식이다


여기선 인접행렬과 인접리스트만 다루겠다

인접리스트

• 각 노드가 자신과 연결된 노드를 리스트로 저장한다

특징

• 공간 효율이 좋다

• 가중치도 저장 가능하다
  
  
  

인접행렬

• 2차원 배열인 행렬을 사용해 노드 간 연결 여부를 저장한다

• graph[x][y] 가 1이면 x에서 y로 가는 엣지가 있는 것이고 0이면 없는것이다

특징

• 구현이 간단하며 접근이 빠르다

• 행렬이기에 N x N으로 공간낭비가 있다

• 무뱡향 그래프일시에 대칭 행렬이다

간단히 비교

| 항목 | 인접행렬 | 인접리스트 | | ——— | ———— | ——————— | | 구조 | 2차원 배열 N×N | 배열 + 연결 리스트 | | 공간 복잡도 | O(N²) | O(N + E) (E: 엣지 수) | | 연결 확인 속도 | O(1) | O(노드 수) | | 엣지 추가/삭제 | 빠름 (O(1)) | 느릴 수 있음 (O(리스트 길이)) | | 희소 그래프 적합 | ❌ 비효율적 | ✅ 효율적 | | 구현 난이도 | ✅ 간단 | 🔺 다소 복잡 |