그래프는 연결되어 있는 객체 간의 관계를 표현한 자료구조이다.
이전에 다루었던 트리 역시 그래프의 일종이다.

1. 그래프 정의

그래프 G를 (V, E)로 표시한다.

1. V는 정점(Vertices)으로 노드(node)라 하며, 여러 특성을 가질 수 있는 객체를 의미한다.
   • V(G): 그래프 G의 정점들의 집합
     
     
2. E는 간선(Edge) 또는 링크(link)라 하며, 정점들 간의 관계를 의미한다.
   • E(G): 그래프 G의 간선들의 집합

다음 그림의 두 그래프는 같은 그래프이다.

1. 그래프 종류

그래프는 간선의 종류에 따라 다음의 두 그래프로 나눌 수 있다.

1. 무방향 그래프 (undirected graph)
   • 간선을 통해서 양방향으로 갈 수 있다.
   • (A, B) = (B, A)
     
     
     
2. 방향 그래프 (directed graph)
   • 간선을 통해서 단방향으로만 갈 수 있다.
   • <A, B> != <B, A>
     

또한 그래프의 간선에 가중치를 넣어서 그래프를 표현할 수 있는데,
이러한 그래프를 가중치 그래프라 한다.

// 간선에 비용(cost)이나 가중치(weight)가 할당된 그래프

3. 그래프 표현 (인접행렬, 연결리스트)

그래프는 인접행렬과, 인접 리스트로 표현이 가능한데
C++ 객체로 구현한 그래프는 DFS, BFS 알고리즘에서 정의하였다.