그래프는 노드(node)와 에지(edge)로 구성된 자료구조입니다.
아래 그림은 동그라미가 노드이고 실선이 에지인 무향 그래프입니다.

그래프의 종류

무향 그래프

• 에지에 방향이 없는 그래프입니다.
• 방향이 없으므로 A 에서 B로 B에서 A로 이동할 수 있습니다.
• 두 노드가 서로 연결되어 있음을 의미하며 그 길을 경로라고 합니다.

방향 그래프

• 에지에 방향이 있는 그래프입니다.
• 해당 방향으로만 이동할 수 있습니다.

그래프 나타내기

아래의 방향 그래프를 표현하는 두 방식을 알아보겠습니다.

1. 인접 행렬

인접행렬은 그래프를 가장 쉽게 표현하는 방식으로, 정사각형 모양의 2차원 배열로 나타냅니다. 배열의 각 인덱스는 노드를 의미하고, 원소는 각각의 노드에 에지가 있으면 true 없으면 false로 나타냅니다.

2. 인접 리스트

인접 리스트는 노드에 연결된 노드들을 리스트로 표현하는 방식입니다. 이 방식은 원소가 리스트인 1차원 배열로 표현할 수 있습니다.