📌 DFS(Depth-First-Search)

: 깊이 우선 탐색
루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전 해당 분기를 완벽히 탐색하는 방법
(한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와 이곳으로부터 다른 방향으로 다시 탐색을 진행)
➡ 깊게 탐색 후 넓게 탐색(찾고자하는 노드가 깊이 있을 때 유리)
BFS보다 간단하지만 속도는 BFS보다 느림

🔎 특징

• 자기 자신을 호출하는 순환 알고리즘 형태
• 이 알고리즘을 구현할 때 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함.(검사하지 않을 경우 무한 루프에 빠질 위험)
  

🔎 시간 복잡도

정점의 수: N, 간선의 수: E
인접 리스트로 표현된 그래프: O(N+E)
인접 행렬로 표현된 그래프: O(N^2)

📌 BFS(Breadth-First-Search)

: 너비 우선 탐색
로트 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하느 순회 방법
➡ 넓게 탐색 후 깊게 탐색(두 노드 사이 최단 경로 찾을 때 유리)

🔎 특징

• 재귀적으로 동작하지 않음
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함. 검사하지 않을 경우 무한 루프 위험
• BFS는 방문한 노드들을 차례로 저장 후 꺼낼 수 잇는 자료구조인 Queue를 사용(FIFO, 선입선출)
  

---

내용/사진
참고 사이트 https://yunyoung1819.tistory.com/86