그래프는 지금까지 소개된 자료구조 중에서 표현 능력이 가장 강력한 비선형 자료구조이다.

→ 그래프는 노드 사이의 관계에 아무런 제약이 없다!

• 다음 노드뿐 아니라 이전 노드도 여러 개 올 수 있다.

→ 따라서 그래프는 객체 사이의 연결 관계를 표현하기에 적합한 자료구조이다.

• 그래프는 객체들 사이의 다대다 관계도 표현할 수 있다.
  • 즉, 그래프를 이용하면 리스트, 트리 등도 저장할 수 있다.

1. 그래프란?

→ 그래프는 노드(node)와 간선(edge)의 집합이다.

• 노드(정점) = 저장하려는 자료의 단위
• 간선 = 노드 사이를 연결하는 선
  • 트리의 제약과는 달리, 이전 노드가 여러 개 올 수 있다.

• 방향 그래프 : 그래프의 간선에 방향이 있는 그래프
  • 양방향 통행을 나타내기 위해서는 양쪽으로 각각 간선이 있어야 한다.