그래프를 저장하는 방법?

그래프는 정점과 간선으로 이루어져있으니 정점을 저장하고 간선을 저장해야 합니다.

정점 6개, 간선 8개

• 정점의 저장 : 개수 V

  • 1 ~ V or 0 ~ V-1
  • 꼭 1이나 0으로 시작하지 않아도 충분히 0,1로 바꿀 수 있기 때문에 정점을 저장할 때는 개수가 중요합니다.

• 간선의 저장 : 개수 E

  • 단, 정점과는 다르게 개수만 알고 있다고 해도 어디가 연결되어있는지 모릅니다.
  • 그래서 “간선을 어떻게 저장할 것이냐?” 는게 가장 중요한 포인트입니다.

• 그래프의 간선의 방향에 따라서 2가지로 나뉩니다.

  1. 방향그래프
  2. 양방향그래프

  만일 양방향 그래프라면 방향그래프에서 2 → 3으로 가는것과 3 → 2로 가는 것을 같이 저장해야 합니다.

그렇다면 간선을 효율적으로 저장하는 방식을 찾아야 합니다.

<aside> 💡 효율적으로 저장하는 방법은 2가지

1. 인접 행렬
   • 2차원 행렬을 이용해서 저장 (배열을 사용해서 저장)
2. 인접 리스트
   • 리스트를 이용해서 저장, 하나의 정점과 연결된 모든 정점을 저장하는 방식 </aside>

1. 인접행렬

정점의 개수가 V라면 V * V크기의 배열을 이용

A[i][j] = 1이면 i → j 간선이 있음

A[i][j] = 0이면 i → j 간선이 없음

인접행렬을 넣는 방식