Depth-first search

Depth-first search (DFS) is a graph traversal method in combinatorics that goes as far as it can down one branch before backtracking. It is used to explore paths, detect cycles, and study connectivity in graphs and trees.

What is Depth-first search?

Depth-first search, or DFS, is a way to walk through a graph in combinatorics by following one route as far as possible before turning around and trying another branch. You mark a starting vertex, move to an unvisited neighbor, keep going deeper, and only backtrack when you get stuck.

That makes DFS different from a random walk. It is systematic, so every vertex and edge can be checked without losing track of where you came from. In a tree, DFS keeps drilling down a branch until it reaches a leaf, then returns to the nearest vertex that still has an unexplored neighbor.

DFS can be written recursively or with an explicit stack. The recursive version is common in class because the call stack naturally stores the path you are currently exploring. The stack version does the same job by hand, which is useful when you want to see the order of visits more clearly.

In graph theory problems, DFS is often less about the exact order of visited vertices and more about what that order reveals. If you find a vertex again through a non-parent edge, that can signal a cycle. If DFS starting from one vertex cannot reach every other vertex, the graph is disconnected and you can repeat the search on another unvisited vertex to find the connected components.

A compact example helps: suppose a graph has vertices A, B, C, D, and E, with edges A-B, A-C, B-D, and C-E. If you start at A and choose B first, DFS may visit A, B, D, then backtrack to A, then visit C, then E. The exact order can change if you pick C before B, but the depth-first pattern stays the same.

Why Depth-first search matters in COMBINATORICS

DFS matters in combinatorics because many graph problems are really questions about structure, reachability, and hidden patterns. When you can trace a graph depth-first, you can check whether the graph is connected, split it into connected components, or spot whether a cycle exists.

It also shows up in bigger ideas from the course. Hamiltonian path questions often involve systematic search through possible routes, and DFS gives you the backtracking mindset behind that search. For Eulerian-style problems, the traversal idea helps you reason about how edges are used and why some networks can be covered cleanly while others cannot.

In weighted graph topics, DFS is not the main tool for finding a minimum spanning tree, but it still helps you understand how a spanning structure spreads through a graph. It is also useful when graphs are stored as adjacency lists or matrices, because you need a clear rule for how to move from one vertex to the next.

A lot of graph work in combinatorics is about proving something exists or showing that something cannot happen. DFS gives you a clean, repeatable way to do that. Instead of guessing, you can trace the graph branch by branch and turn the picture into a precise argument.

How Depth-first search connects across the course

Graph Traversal

DFS is one of the main graph traversal methods, along with breadth-first search. Traversal is the broader idea of visiting vertices and edges in a controlled order. In combinatorics, the choice of traversal changes what you notice first, like long chains, nearby neighbors, or disconnected pieces.

Backtracking

DFS naturally uses backtracking because you return to the last vertex with an unexplored option after a branch ends. That is why DFS is such a good mental model for search problems. When a graph question asks you to try possibilities without missing any, backtracking is the logic behind the process.

Graph Connectivity

A DFS from one vertex can show which vertices are reachable from it, so it is a direct tool for testing connectivity. If some vertices never get marked, the graph is disconnected. Repeating DFS on each unvisited vertex is how you identify connected components.

Cut Edge

DFS can help detect bridge-like edges, also called cut edges, because it reveals whether removing an edge breaks access to part of the graph. In connectivity problems, that matters when you want to know which edges are structurally fragile. DFS gives you the exploration order needed to spot those weak links.

Is Depth-first search on the COMBINATORICS exam?

A graph problem set might ask you to list the order of vertices visited by DFS, identify whether a cycle appears, or determine the connected components of a drawing. Your job is to follow the rule, go as deep as possible before backtracking, and keep track of which vertices are already visited.

If the graph is given as a picture, start at the stated vertex and choose an unvisited neighbor consistently, usually the leftmost, smallest-labeled, or as-specified option. If the graph is given by an adjacency list or matrix, convert that information into a clear visit order before you trace the search.

On written work, the full answer is often not just the final set of visited vertices. You may need to show the path taken, explain why a cycle was detected, or justify why a graph has more than one component. If your course uses proofs or short explanations, DFS is often the tool behind the reasoning rather than the final conclusion itself.

Depth-first search vs Breadth-first search

DFS goes down one branch before trying others, while breadth-first search explores all neighbors level by level. The difference matters because BFS is better for shortest-path style thinking in unweighted graphs, but DFS is often better for backtracking, cycle checks, and connectivity questions.

Key things to remember about Depth-first search

• Depth-first search is a graph traversal method that explores one branch fully before backtracking to the next option.

• In combinatorics, DFS is useful for checking connectivity, finding connected components, and spotting cycles in a graph.

• You can run DFS recursively or with a stack, and both versions keep track of the current search path.

• The exact visit order can change depending on which neighbor you choose first, but the depth-first rule stays the same.

• DFS is a thinking tool for graph problems, not just a coding method, so it often supports proofs and hand-traced solutions.

Frequently asked questions about Depth-first search

What is depth-first search in Combinatorics?

Depth-first search is a graph traversal method where you keep moving to unvisited neighbors until you cannot go any farther, then you backtrack. In combinatorics, it is used to explore graphs and trees in a disciplined way, especially for connectivity and cycle questions.

How is depth-first search different from breadth-first search?

DFS goes deep along one branch before switching, while breadth-first search checks all nearby vertices first. That makes DFS better for backtracking-style problems and structure checks, while BFS is the method people usually think of for shortest routes in unweighted graphs.

How do you use DFS to find connected components?

Start DFS at one unvisited vertex and mark everything you can reach. When that search finishes, any still-unvisited vertex belongs to a different connected component, so you start again there and repeat until every vertex is marked.

Can DFS find cycles in a graph?

Yes. If DFS reaches a vertex that has already been seen and it is not just the edge you came from, that suggests a cycle. In class problems, this is one of the fastest ways to reason about whether a graph has a loop.