그래프를 탐색하는 방법에는 크게 너비우선탐색(BFS) 과 **깊이우선탐색(DFS)**가 있다

그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종

그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

그래프와 트리의 차이점은 그래프 중에서 방향성이 있는 비순환 그래프를 트리라고 함

1. 너비 우선 탐색 (BFS, Breath-First Search)

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

너비 우선 탐색의 개념

루트노트(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방정.

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용

2. 깊이 우선 탐색(DFS, Depth-First Search)

최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동

깊이 우선 탐색의 개념

루트노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에