인접 행렬과 인접 리스트

인접행렬 (Adjacency Matrix)

• 정의
  정점 간의 연결 관계를 2차원 배열로 표현한 방식입니다.
  bool 타입의 정사각형 행렬로, 크기는 V x V (정점 개수 V)입니다.
• 특징
  • graph[i][j] = 1이면 i번 정점과 j번 정점 사이에 간선이 존재
  • graph[i][j] = 0이면 간선이 존재하지 않음
  • 간선이 없는 경우에도 모든 정점 쌍에 대해 공간을 차지함
• 복잡도
  • 공간 복잡도: O(V^2)
  • 간선 존재 여부 확인: O(1)
  • 인접 정점 순회: O(V)

인접리스트 (Adjacency List)

• 정의
  각 정점에 연결된 정점들을 리스트로 저장한 방식입니다.
  보통 배열이나 해시맵을 사용하여 각 정점 번호에 연결된 리스트를 매핑합니다.
• 특징
  • 연결된 정점만 리스트에 저장하므로 불필요한 공간 낭비가 없음
  • 희소 그래프(간선 수가 적은 그래프)에 유리
• 복잡도
  • 공간 복잡도: O(V + E)
  • 간선 존재 여부 확인: O(V) (최악의 경우)
  • 인접 정점 순회: O(인접한 정점 수) (보통 빠름)
• 리스트 연산 정리
• 
  

  연산	시간 복잡도
  n번째 인덱스 삽입/삭제	O(1) (단, 포인터 알고 있을 경우)
  마지막 요소 삽입/삭제	O(1)
  특정 요소 탐색	O(n)
  n번째 요소 참조	O(n)

인접행렬 vs 인접리스트

비교 항목	인접 행렬	인접 리스트
공간 복잡도	O(V^2)	O(V + E)
간선 탐색	O(1) (빠름)	O(V) (느릴 수 있음)
정점 탐색	모든 정점 순회 필요: O(V)	연결된 정점만 순회: 빠름
밀집 그래프	효율적	비효율적
희소 그래프	비효율적	효율적