Q. 개념

전략

• 그래프를 나타내는 기호 : G(V, E)

  G(그래프)는 V(노드)와 E(간선)으로 이루어짐

• 무방향 그래프 (= 양방향 그래프)
  - 입력 예시 (왼쪽을 a, 오른쪽을 b 변수로 받을 때)

  1 2
  1 3
  2 4
  3 4
  2 5

  -그래프를 인접행렬(2차원배열)로 표현

  graph[a][b] = 1;
  graph[b][a] = 1;

  ::: 1 2 3 4 5
  1 0 1 0 0 0
  2 1 0 0 0 0
  3 0 0 0 0 0
  4 0 0 0 0 0
  5 0 0 0 0 0
  => 행을 돌면서 값이 1인 열이 있으면 간선이 존재하는 것

• 방향 그래프
  - 입력 예시 (왼쪽을 a, 오른쪽을 b 변수로 받을 때)

  // 방향 순서대로 입력 됨을 전제
  1 2 // 1->2
  1 3
  3 4
  4 2
  2 5

  -그래프를 인접행렬(2차원배열)로 표현

  // a (행) -> b (열)
  graph[a][b] = 1;
  
  ::: 1 2 3 4 5
  1 0 1 0 0 0
  2 0 0 0 0 0
  3 0 0 0 0 0
  4 0 0 0 0 0
  5 0 0 0 0 0
  => 행을 돌면서 값이 1인 열이 있으면 간선이 존재하는 것

• 가중치 방향 그래프
  - 입력 예시 (왼쪽을 a, 가운데를 b, 오른쪽을 c 변수로 받을 때)

  1 2 2 // 1->2이면서 가중치가 2
  2 5 5
  4 2 2
  1 3 4
  3 4 5

  -그래프를 인접행렬(2차원배열)로 표현

  // a (행) -> b (열)
  graph[a][b] = c;
  
  ::: 1 2 3 4 5
  1 0 2 0 0 0
  2 0 0 0 0 0
  3 0 0 0 0 0
  4 0 0 0 0 0
  5 0 0 0 0 0
  => 행을 돌면서 값이 0보다 큰 숫자(가중치)인 열이 있으면 간선이 존재하는 것

✅ arr[행][열]