沿一支深入再回溯
深度优先搜索访问一个顶点后，先选取尚未访问的邻居继续深入；等这条递归分支处理结束，再回到原顶点寻找其他邻居。递归调用保存了尚待继续的位置，也可以用显式栈组织相应状态。
进入一个顶点时先标记，可以阻止环或多条来路导致无限重复访问。标记表示已经发现过这个顶点，不表示它的所有后继工作都已经完成；“进入”和“完成”在许多后续分析里需要分别记录。
得到可达证据与遍历森林
记录首次访问的前驱，可以从任意已到达顶点回溯到起点，得到一条实际路径。深度优先首先沿当前分支深入，因此先找到的路径可能很绕；需要无权图中的最少边数时，通常应选择广度优先搜索。
若要处理整张不连通的图，可以在一次搜索结束后，从仍未标记的顶点重新开始，形成一片搜索森林。在无向图里，这也能为不同连通分量编号；有向图的相互可达则需要额外的强连通分析。
开始与完成次序有不同用途
先记录顶点再递归，可以得到先序；等它的递归分支处理完再记录，则得到后序。在有向无环图中，后序反转能形成满足依赖方向的拓扑顺序，关键是图的无环条件与完成次序共同起作用。
用邻接表扫描有限图时，时间可控制在O(V+E)。但递归深度可能与最长搜索分支相关，极端情况下接近顶点总数；处理很深的图时，需要把调用栈容量或显式栈设计纳入资源评估。