> For the complete documentation index, see [llms.txt](https://aloy.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aloy.gitbook.io/notes/dsa/algorithms/dfs.md).

# dfs

## Depth First Search (DFS)

Graph traversal method

Uses **STACK**

**VERTICAL then HORIZONTAL**

![dfs vs bfs.gif](https://3935715743-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FBH37CsSwZp9OqLuOogCr%2Fuploads%2Fgit-blob-3d05ecb1508dd44f7b85973fb397c251bc03a5d0%2Fdfs_vs_bfs.gif?alt=media)

## How?

> In a DFS, we always explore the deepest node; that is, we go one path as deep as possible, and if we hit the dead end, we back up and try a different path until we reach the end.

![Untitled](https://3935715743-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FBH37CsSwZp9OqLuOogCr%2Fuploads%2Fgit-blob-6708bd32d93b1c1daf1514392a4f7c525decf6d3%2FUntitled%2037.png?alt=media)

* Uses a stack to remember where it should go
* Application :
  * Cycle detection :\
    Encounter new edge that points to already visited vertex = cycle
  * Finding connected components
  * Topological sort
  * Maze Generation