인접행렬 (Adjacency Matrix)

핵심 개념: 인접 행렬은 그래프에서 각 정점 간의 연결 상태를 나타내는 2차원 배열입니다.

구성 요소

1. 행과 열: 정점들이 행과 열로 표시됩니다. 행과 열의 인덱스가 그래프의 정점을 나타냅니다.
2. 값의 의미
   • 배열의 각 요소는 두 정점 사이의 연결을 나타내며, 값이 1이면 연결됨을 의미하고 0이면 연결되지 않음을 의미합니다.
   • 가중치가 있는 그래프에서는 가중치 값을 사용하여 연결을 표시할 수 있습니다.
3. 인접 행렬 예시
   1. • 장점:
        • 연결 여부를 O(1) 시간에 확인할 수 있습니다.
        • 밀도가 높은 그래프에서는 효율적입니다.
      • 단점:
        • 정점이 많고 간선이 적을 때 공간 낭비가 큽니다. 가령, 정점 A, B, C, D로 이루어진 그래프가 있다고 가정하겠습니다.

          A	0	1	0	1
          B	1	0	1	0
          C	0	1	0	1
          D	1	0	1	0

          • A-B, A-D, B-C, C-D는 연결되어 있습니다.
          • B-A, D-C 등 반대 방향도 연결되어 있어 대칭을 이룹니다.
          장단점
4. 요약: 인접 행렬은 정점 간의 연결 상태를 간단하게 2차원 배열로 나타낼 수 있으며, 연결 여부를 빠르게 확인할 수 있는 장점이 있습니다.