由于这个答案中给出的现有非递归DFS实现似乎有问题，所以让我提供一个实际可行的实现。
我用Python编写了这个实现，因为我认为它非常易读且没有实现细节的混杂（并且因为它具有实现生成器的便捷关键字yield），但是将其移植到其他语言应该相当容易。
def find_simple_paths(graph, start, end):
visited = set()
visited.add(start)
nodestack = list()
indexstack = list()
current = start
i = 0
while True:
neighbors = graph[current]
while i < len(neighbors) and neighbors[i] in visited: i += 1
if i >= len(neighbors):
visited.remove(current)
if len(nodestack) < 1: break
current = nodestack.pop()
i = indexstack.pop()
elif neighbors[i] == end:
yield nodestack + [current, end]
i += 1
else:
nodestack.append(current)
indexstack.append(i+1)
visited.add(neighbors[i])
current = neighbors[i]
i = 0
这段代码维护着两个平行的栈：一个包含当前路径中较早的节点，另一个包含每个节点在节点栈中的当前邻居索引（这样我们就可以在将其从栈中弹出时恢复遍历节点的邻居）。我本可以使用单个(node, index)对的栈，但我认为两个栈的方法更易读，也许对其他语言的用户更容易实现。
此代码还使用了一个单独的“visited”集合，它始终包含当前节点和栈上的任何节点，以便让我高效地检查节点是否已经是当前路径的一部分。如果你的语言恰好有一个“有序集合”数据结构，它提供了高效的类似栈的推/弹操作和高效的成员资格查询，你可以将其用于节点栈并摆脱单独的“visited”集合。
或者，如果您正在使用自定义可变类/结构来表示节点，则可以在每个节点中存储一个布尔标志，以指示它是否已作为当前搜索路径的一部分被访问。当然，这种方法不能让您在同一图上并行运行两个搜索，如果您由于某种原因希望这样做。
以下是一些测试代码，演示了上面给出的函数如何工作：
graph = {
"A": ("B", "C"),
"B": ("A", "C", "D"),
"C": ("A", "B", "D"),
"D": ("B", "C"),
}
for path in find_simple_paths(graph, "A", "D"): print " -> ".join(path)
在给定的示例图上运行此代码会产生以下输出：
A -> B -> C -> D
A -> B -> D
A -> C -> B -> D
A -> C -> D
请注意，虽然此示例图是无向的（即所有边都双向），但该算法也适用于任意有向图。例如，通过删除
C -> B 边缘（通过从
C 的邻居列表中删除
B）可以获得相同的输出，除了第三条路径（
A -> C -> B -> D），这不再可能。
附注：构建一些图形很容易使得像这个（以及本帖中给出的其他算法）这样的简单搜索算法表现非常差。
例如，考虑在无向图上查找从A到B的所有路径的任务，其中起始节点A有两个邻居：目标节点B（除了A之外没有其他邻居）和一个由n+1个节点组成的团体的节点C，如下所示：
graph = {
"A": ("B", "C"),
"B": ("A"),
"C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),
"H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),
"I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),
"J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),
"K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),
"L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),
"M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),
"N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),
"O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),
}
很容易看出A和B之间的唯一路径是直接的，但从节点A开始的天真DFS将浪费O（
n！）时间在团中探索无用的路径，即使对于人类来说，这些路径显然都不可能通向B。
人们还可以构造具有类似特性的
DAGs，例如通过使起始节点A连接目标节点B和另外两个节点C
1和C
2，这两个节点都连接到节点D
1和D
2，这两个节点又连接到E
1和E
2，依此类推。对于像这样排列的
n层节点，搜索所有从A到B的路径的天真搜索最终将浪费O(2
n)时间，在放弃之前检查所有可能的死路。
当然，从团中的一个节点（C 以外的节点）或者 DAG 的最后一层向目标节点 B 添加边将会导致从 A 到 B 可能出现指数级数量的路径，一个纯粹的局部搜索算法事实上无法预先知道是否会找到这样的边。因此，在某种程度上，这种天真搜索的不良
输出敏感性 是由于它们缺乏对图形全局结构的认识。
虽然有各种预处理方法（例如迭代地消除叶节点、寻找单节点顶点分隔器等）可以用来避免一些这样的“指数时间死胡同”，但我不知道有任何通用的预处理技巧可以在
所有情况下消除它们。一种通用解决方案是在搜索的每一步检查目标节点是否仍然可达（使用子搜索），如果不能，则尽早回溯，但遗憾的是，对于许多不包含这种病态死胡同的图形来说，这将显著减慢搜索速度（在最坏情况下，与图形大小成比例）。
