그래프(graph)

: 연결의 집합을 모형화한 것

즉, 항목들이 서로 어떻게 연결되어 있는지를 모형화하는 방법

구성

• 정점(vertex) / 노드(node)
• 간선 (edge)

특징

• 노드는 여러 개의 다른 노드와 바로 이어질 수 있음 ⇒ 이웃(neighbor) = 바로 이어진 노드
• 루트 노드, 부모-자식의 개념 없음

종류

• 무방향 그래프 (undirected graph)

  : 간선을 통해서 양방향으로 갈 수 있음

  Ex)

  • 양방향 통행 도로
  • (A, B) = (B, A)

• 방향 그래프(directed graph)

  : 간선에 방향성이 존재

  Ex)

  • 일방통행

  • A → B 로만 갈 수 있는 경우

    이러한 경우, (A, B) ≠ (B, A)

구현 방법

인접 행렬 (Adjacency Matrix)

• 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타냄.
  • 즉, 파이썬에서는 이차원 리스트 사용

$$ adi[i][j] = 1 if ~\exist ~edge~s.t. node ~i \rightarrow~node~j \newline adi[i][j] = 0 o.w.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ $$

• 무방향 그래프의 경우 대칭행렬이 됨