[TIL]DFS,BFS

텍스트그래프 탐색 방법에는 크게 두가지가 있다.

여기서 그래프란,정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며,그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

사실 트리도 그래프의 한 종류이다. 두 자료 구조 모두 서로 연결되는 노드로 구성된다.

그래프와 트리의 차이는 무엇일까?

모든 트리는 그래프이지만, 그래프가 모두 트리는 아니다.

구체적으로 말하면 트리로 규정되는 그래프에는 사이클(cycle)이 있을 수 없으며 모든 노드가 서로 연결되어야 한다.

깊이 우선 탐색 (DFS)

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

깊이 우선 탐색의 개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다.

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서느림

너비 우선 탐색 (BFS)

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

너비 우선 탐색의 개념:

루트노드(혹은 다른 임의의 노드) 에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가장 가까운 정점을 방문하고멀리 떨어져 있는 정점을 가장 나중에 방문하는 탐색 방법이다.

DFS와 BFS의 시간복잡도두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다. DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.