📌Today I Learned

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

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
넓게 탐색하기 전에 깊게 탐색하는 것.
완전 탐색
BFS보다 간단하다.
단순 검색 속도는 BFS보다 느리다.

특징

자기 자신을 호출하는 순환 알고리즘의 형태를 가진다.
전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
어떤 노드를 방문했는지 여부를 검사해야한다.(안그러면 무한루프)
백트래킹을 통해 탐색하지 않은 정점이 있는지 확인한다.

시간복잡도

DFS는 그래프(정점의 수: N, 간선의 수:E)의 모든 간선을 조회한다.

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)
  => 그래프 내에 적은 숫자의 간선만 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

참고
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html