Suggest an editImprove this articleRefine the answer for “What does depth-first search (DFS) do?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)**Depth-First Search (DFS)** is an algorithm that explores a graph as deeply as possible along each path before backtracking. **Key point:** DFS is a "deep" search with backtracking, which traverses a graph by following a path to the end before moving to other branches.Shown above the full answer for quick recall.Answer (EN)Image**Depth-First Search (DFS)** is an algorithm that **explores a graph as deeply as possible along each path** before backtracking. --- ### Idea DFS goes "deep", from the starting vertex to the first neighbor, then to that neighbor's neighbor, and so on, until it reaches a vertex with no unvisited neighbors left. Then it **backtracks** and continues with other vertices. --- ### Step by step (recursive version) 1. Start from the starting vertex and mark it as visited. 2. For each neighbor of this vertex: - If the neighbor is not visited, run DFS on it. 3. Continue until all reachable vertices have been visited. --- ### Example For the graph ```javascript A - B - C | | D - E ``` If you start from **A**, one possible traversal order is: **A → B → C → E → D** (The exact order depends on the order of neighbors in the data structure.) --- ### Implementation - Uses a **stack**, implicitly through recursion or explicitly through a data structure. --- ### Applications - Checking a graph's **connectivity**. - Finding **cycles**. - **Topological sorting** (in directed graphs). - Finding paths, connected components, "islands", and so on. --- **Summary:** DFS is a **"deep" search with backtracking**, which traverses a graph by following a path to the end before moving to other branches.For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.