1. 그래프의 개념
그래프란 정점들이 간선으로 연결된 자료구조를 말한다. 간선에 대한 제한은 없으며, 간선에 방향이 있는 방향 그래프와 간선에 방향이 없는 무방향 그래프가 있다. 정점에 연결된 간선의 개수를 차수라고 한다.
2. 그래프의 구현
그래프를 구현하는 방법은 많지만 이 글에서는 연결 리스트로 구현하는 방법만을 다룬다. 우선 정점들을 포인터 변수에 저장한다. 그리고, 각 포인터 변수에는 간선으로 연결된(이웃한) 정점들의 주소를 저장한다. 이웃한 정점이 2개 이상이라면, 이를 연결 리스트 형식으로 이어준다.
3. 그래프의 연산
1) 깊이우선 탐색(DFS)
깊이 우선 탐색이란 한 우물을 깊게 파는 방식과 비슷하다. 한 정점에서 시작해 이웃한 정점 중 하나를 방문하고, 그 정점에서 이웃한 정점을 방문한다. 이를 반복하다 더는 방문할 정점이 없다면, 바로 전에 방문한 정점으로 가 과정을 반복한다.
2) 넓이우선 탐색(BFS)
넓이 우선 탐색은 많은 우물을 얕게 파는 것과 같다. 한 정점에서 시작해 모든 이웃한 정점을 방문한다. 이후, 방문한 정점들과 이웃한 정점들을 모두 방문한다. 더는 방문할 정점이 없을때 까지 이를 반복한다.