그래프는 선형 자료 구조가 아니기 때문에 모든 노드를 한 번만 방문하는 순회(traversal)를 구현하기가 쉽지 않습니다. 그래프의 모든 노드를 순회하는 방법은 두 가지입니다. 너비 우선 탐색(Breadth First Search, BFS)과 깊이 우선 탐색(Depth First Search, DFS)입니다. 너비 우선 탐색은 큐를 이용해서 구현하고, 깊이 우선 탐색은 스택을 기반으로 합니다. 이 둘은 많은 알고리즘에서 기본적으로 사용하고 있기 때문에 매우 중요합니다.

이 절에서 만들 그래프는 이전 절에서 만든 그래프를 사용하지 않을 것입니다. 앞으로 공부하게 될 많은 그래프 알고리즘은 add_vertex나 delete_vertex, delete_edge 연산이 필요 없습니다. 한번 그래프가 완성되면 이후 정점이나 에지가 바뀔 일이 거의 없기 때문입니다.

먼저 너비 우선 탐색을 알아보겠습니다.