What does depth-first search (DFS) do?

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

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.