A way of searching a graph or tree that goes as far as possible along one path and backtracks to try another path when it reaches a dead end. It is implemented with recursion or a stack and is used for maze solving, finding connected components and cycles, and topological sorting. It is abbreviated DFS.
Japanese name: 深さ優先探索
Depth-first search appears in 3 practice questions across 1 topic, including Data Structures and Algorithms.
Answer: C. A, B, D, E, F, C
From A the search moves to B, then to D, the first unvisited neighbor of B. D's only neighbor, B, is already visited, so it returns to B and moves on to E, then from E to the unvisited F, and from F to its neighbor C. The order is therefore A, B, D, E, F, C. A, B, C, D, E, F is the breadth-first search order, which visits vertices nearest-first. A, B, D, E, C, F turns back from E without going to the unvisited F, so it is not a depth-first order.
Depth-first search (using recursion or a stack) goes as far as it can along one path, so it may first reach a vertex by a roundabout route, and shortest distances are not guaranteed.
In a graph whose edges have no weights, you want to find th…Topological sorting arranges the vertices of a directed acyclic graph (DAG) so that every edge points from earlier to later; it can be done by repeatedly taking a vertex with no incoming edges (Kahn's algorithm) or with depth-first search.
Tasks A to E have the ordering constraints “A before C”, “B…As an Amazon Associate I earn from qualifying purchases.
Breadth-first search Queue Recursion Stack Binary heap Binary search Binary search tree Dijkstra's algorithm Dynamic programming Greedy algorithm