인접행렬 저장

• N : 정점의 총 수
• N x N 행렬로 표현
  • 원소 ( i, j ) = 1 : 두 원소 사이에 간선 있음
  • 원소 ( i, j ) = 0 : 두 원소 사이에 간선 없음
• 방향 그래프일 때
  • 원소 ( i, j ) = i 로 부터 j 로 연결되는 간선이 있는가?
• 가중치 있는 그래프
  • 원소 ( i, j )는 1 대신 가중치를 가짐

무방향

무방향 + 가중치

방향

방향 + 가중치

인접 리스트

• N 개의 연결 리스트로 표현
• i 번째 리스트는 정점 i 에 인접한 정점들을 리스트로 연결해 놓음