그래프 순회

• 한 정점에서 시작해서 그래프에 있는 모든 정점을 한번씩 방문하는 것을 그래프 순회 또는 탐색이라고 한다.

깊이 우선 탐색

• 깊이 우선 탐색(Depth First Search : DFS)은 어떤 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하며 순회하는 방법으로 스택을 사용한다.
• 갈 수 있는 곳이 더 이상 없을 때까지 가는 것이고, 더 이상 갈 곳이 없어지면 탐색한 순서대로 되돌아간다.
  

너비 우선 탐색

• 너비 우선 탐색(Breadth First Search : BFS)은 가까운 정점을 모두 차례로 방문한 후 점점 먼 정점을 방문하는 방식으로 큐를 사용한다.
  
  

순회 알고리즘

• 시작 정점을 스택/큐에 저장한다.

1. 스택 혹은 큐에는 다음에 방문할 정점이 저장

• 스택/큐가 비워질 때까지 아래를 반복한다. (그래프 전체를 순회할 때까지)

1. 다음 방문할 정점을 가져옴
2. 방문했다는 정보를 저장
3. 방문해서 해야할 일을 수행
4. 방문하지 않은 인접한 정점을 스택/큐에 저장