LESSON 06 OF 08Graph DFS
0% learnt
GRAPH DEPTH-FIRST SEARCH · STACK AND VISITED SET
DFS begins at A. What must happen before following an edge?
Marking on entry prevents another route from adding A again later.
RULE TO APPLYMark first, descend to one unvisited neighbor, backtrack only at a dead end.
LIVE ALGORITHM STATEVisited is empty until A is marked.
RECURSION STACK
A
LESSON 061 / 2
REAL INTERVIEW PROBLEMFollow one route until it ends, then backtrack.
Visit every vertex reachable from A in a graph that contains cycles, without visiting any vertex twice.
INPUTstart = A; edges = A-B, A-C, B-D, D-C, C-EOUTPUT[A, B, D, C, E]
WHAT YOU WILL DOMark each vertex before descending, choose an unvisited neighbor, and backtrack when no unvisited neighbor remains.