DFS & BFS

둘다 그래프 자료구조의 전체 노드를 방문할 수 있는 탐색 알고리즘이다.

DFS

1. 깊이 우선 탐색으로 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 반복
   

방문한 곳에서 다시 DFS 알고리즘을 실행하는 재귀함수의 구조로 코드를 짜야 가시적이고 편리한 편이다.

BFS

1. 너비 우선 탐색으로 첫 방문 노드의 연결되어 있는 모든 노드를 큐에 삽임하고 방문 처리를 한다.
2. 큐에서 차례로 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번 반복.
   

알고리즘 그대로 코드를 작성한 것을 볼 수 있다.

bfs는 노드끼리 거리가 모드 같은 그래프를 탐색하여 최단 경로를 찾고 싶을 때 유용하게 쓰인다.
특정 노드부터 모든 노드를 방문하며 그 노드까지의 최단 거리 값을 기록하면 처음 방문한 노드로부터의 최단 거리가 모든 노드에 기록된다.