DFS的时间和空间分析因其应用领域而异。在理论计算机科学中，DFS通常用于遍历整个图，并且需要时间为 ,[4]且图的大小是线性的。在这些应用中，它也使用空间 ，最坏的情况是存储当前搜索路径上的顶点堆栈以及一组已经访问过的顶点。因此，在此设置中，时间和空间界限与广度优先搜索相同，选择使用这两种算法中的哪一种较少取决于它们的复杂度，而更多地取决于这两种算法产生的顶点排序的不同属性。
适用于与特定领域相关的DFS应用，例如在人工智能中搜索解决方案或者网络爬虫，要遍历的图通常要么太大而不能完整访问，要么是无限的(DFS可能会遭受不终止)。在这种情况下，搜索仅在有限深度的情况下进行；由于资源有限，例如内存或磁盘空间，通常不使用数据结构来跟踪所有先前访问过的顶点的集合。当在有限的深度中搜索时，时间在扩展顶点和边的数量方面仍然是线性的(尽管由于一些顶点可能被搜索不止一次，而其他顶点根本不被搜索，导致这个数量与整个图的大小不同)，但是DFS的这种变体的空间复杂度仅与深度限制成比例，因此远小于使用广度优先搜索搜索到相同深度所需的空间。对于这样的应用，DFS也更适合选择看起来很可能的分支的启发式方法。当事先不知道合适的深度极限时，迭代深化深度优先搜索以递增的限制顺序重复应用DFS。在人工智能的分析模式下，一个分子因子如果深度大于1，迭代加深会使运行时间增加一个常数因子，在这种情况下，由于每层节点数的几何增长，正确的深度限制是已知的。
DFS也可以用于收集图节点的样本。然而，与不完全的 BFS 相似，不完全的DFS对高度的节点有偏差。
图的深度优先搜索的一种方便的描述是用搜索过程中到达的顶点的生成树来表示的。基于这个生成树，原始图的边可以分为三类:前边缘，它从树的一个节点指向它的一个后代节点，后边缘，它从一个节点指向它先前的节点之一，交叉边缘，不使用前边缘和后边缘。有时树边缘属于生成树本身，树边缘的边与前向边分开分类。如果原始图是无向图，那么它的所有边都是树边缘或后边缘。
如果一个图的顶点的枚举是DFS应用于该图的可能的输出，则称之为DFS排序。 形成带 个顶点的图。 是 的不同元素的列表，对于 ，让 成为最大的 ，如果这样一个 存在，则使 是 的近邻，否则是 。
让 是 的顶点的枚举。如果对所有 , 是顶点 ，则枚举 是DFS排序(有源 )，且 是最大的。 是 的一组近邻。同样地，如果对所有 的 来说，存在有一个 的近邻 使得 ，则 是DFS的一个排序。
也可以使用深度优先搜索对图或树的顶点进行线性排序。有三种常见的方法:
例如，当从节点A开始搜索下面的有向图时，遍历的序列要么是A B D B A C A，要么是A C D C A B A (选择从A第一次访问B还是C取决于算法)。请注意，这里包括以回溯到节点的形式重复访问，以检查它是否仍然有未访问的近邻(即使没有发现的情况下)。因此，可能的先置排序是A B D C和A C D B，而可能的后置排序是D B C A和D C B A，可能的反向后置排序是A C B D和A B C D。
反向后置排序产生任何一个有向无环图的一个拓扑排序。这种排序在控制流分析方面也很有用，因为它通常表示控制流的自然线性化。上图可能表示下面代码片段中的控制流，按A B C D或A C B D的顺序考虑该代码是自然的，但使用A B D C或A C D B的顺序是不自然的。
if (A) then {
B
} else {
C
}
D
输入:图G 和G的顶点v
输出:v 中被标记的可被发现的所有顶点
DFS的递归实现：[5]
1 procedure DFS(G,v): 2 label v as discovered 3 for all directed edges from v to w that are in G.adjacentEdges(v) do 4 if vertex w is not labeled as discovered then 5 recursively call DFS(G,w)
通过该算法发现顶点的顺序被称为字典顺序。
最坏空间复杂度下离散傅里叶变换的非递归实现 (d ):[6]
1 procedure DFS-iterative(G,v): 2 let S be a stack 3 S.push(v) 4 while S is not empty 5 v = S.pop() 6 if v is not labeled as discovered: 7 label v as discovered 8 for all edges from v to w in G.adjacentEdges(v) do 9 S.push(w)
DFS的这两个变体以彼此相反的顺序访问每个顶点的相邻顶点: 递归变体访问的v 的第一个相邻顶点是相邻边列表中的第一个，而在迭代变体中，第一个访问的近邻是相邻边列表中的最后一个。递归实现将按以下顺序访问示例图中的节点: A、B、D、F、E、C、G。非递归实现将访问以下节点：A, E, F, B, D, C, G。
非递归实现类似于广度优先搜索，但有两个不同之处:
^查尔斯·皮埃尔·特雷毛(1859-1882)巴黎的巴黎综合理工学院(X:1876)，法国电报工程师 在2010年12月2日的公开会议上——由教授主讲让·佩尔蒂埃-塞伯特在梅肯学院(勃艮第-法国)–(摘要发表在年报学术版，2011年3月)–ISSN 0980-6032).
^Even, Shimon (2011), Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48, ISBN 978-0-521-73653-4。.
^Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (3rd ed.), Pearson Education, ISBN 978-0-201-36118-6。.
^科曼、托马斯·h、查尔斯·e·莱塞森和罗纳德·L·李维斯特。p.606.
^古德里奇和塔马西亚；科曼、莱瑟森、瑞文斯特和斯坦.
^第93页，算法设计，克莱因伯格和塔多斯.
^Hopcroft, John; Tarjan, Robert E. (1974), "Efficient planarity testing", Journal of the Association for Computing Machinery, 21 (4): 549–568, doi:10.1145/321850.321852。.
^de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), "Trémaux Trees and Planarity", International Journal of Foundations of Computer Science, 17 (5): 1017–1030, arXiv:math/0610935, doi:10.1142/S0129054106004248。.
^Reif, John H. (1985). "Depth-first search is inherently sequential". Information Processing Letters. 20 (5). doi:10.1016/0020-0190(85)90024-9..
^Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer..
^Aggarwal, A.; Anderson, R. J. (1988), "A random NC algorithm for depth first search", Combinatorica, 8 (1): 1–12, doi:10.1007/BF02122548, MR 0951989。.
^Karger, David R.; Motwani, Rajeev (1997), "An NC algorithm for minimum cuts", SIAM Journal on Computing, 26 (1): 255–272, CiteSeerX 10.1.1.33.1701, doi:10.1137/S0097539794273083, MR 1431256。.
暂无