深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。它沿着一条路径深入，直到达到一个没有未访问邻居的节点，然后回溯。DFS可以用于访问图中的每个节点、检查不同节点之间的连接关系。与深度优先搜索相对的是广度优先搜索（BFS），后者在深入下一层之前会先检查当前层的所有邻居。这两种方法都很重要，但DFS允许在尝试其他路径之前尽可能深入地沿着一条路径前进。
DFS会彻底地访问一个路径，然后回溯到具有未访问路径的节点。递归DFS使用调用栈来管理遍历，深入到每个路径中。非递归DFS使用一个单独的栈来维护探索过程，因此没有递归深度问题。DFS的时间复杂度是O(V+E)，空间复杂度是O(V)。DFS在许多事情上都很有用，最常见的包括路径查找、循环检测、拓扑排序和解决谜题。
BFS在深入下一层之前会先探索当前层的所有邻居，而DFS则沿着一个分支进行，然后移动到当前层。
DFS算法涉及尽可能深入地访问节点，然后回溯。以下是逐步解释：从根节点开始搜索，在树的情况下，或者从图中的任意节点开始。标记节点为已访问，对于每个相邻节点，如果它尚未被访问，则递归地访问该节点。当到达没有未访问相邻节点的节点时，回溯到上一个节点并继续该过程。
DFS—深度优先搜索是一个递归算法。要为图实现它，可以使用递归或使用栈的隐式递归。以下是Python实现：
def dfs_recursive(graph, node, visited):
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbour in graph[node]:
dfs_recursive(graph, neighbour, visited)
# 示例用法：
graph = {
'A': ['B', 'C', 'D'],
'B': ['E'],
'C': ['G', 'F'],
'D': ['H'],
'E': ['I'],
'F': ['J'],
'G': ['K']
}
visited = set()
print("DFS traversal using recursive approach:")
dfs_recursive(graph, 'A', visited)
DFS的时间复杂度是O(V + E)，其中V和E分别是顶点和边的数量。在最坏的情况下，每个顶点和边都会被搜索一次。空间复杂度将是O(V)，因为需要跟踪已访问的节点。在递归中，将运行一个递归栈，或者可能将节点推入栈中进行迭代。
深度优先搜索（DFS）在计算机科学和现实世界问题中有多种应用：路径查找、循环检测、拓扑排序、图遍历和连接组件、解决复杂的迷宫和谜题。
假设需要在计算机网络中找到所有路径，以便数据可以正确传输。DFS是一个在图中执行深度优先搜索的算法。它可以用于从特定计算机开始，跟随连接，尽可能远地跟随连接，当不能再跟随连接时回溯。
def find_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if start not in graph:
return []
paths = []
for node in graph[start]:
if node not in path:
new_paths = find_paths(graph, node, end, path)
for p in new_paths:
paths.append(p)
return paths
# 示例用法：
network = {
'Computer1': ['Computer2', 'Computer3'],
'Computer2': ['Computer4'],
'Computer3': ['Computer4', 'Computer5'],
'Computer4': ['Computer6'],
'Computer5': ['Computer6'],
'Computer6': []
}
start = 'Computer1'
end = 'Computer6'
print(f"All paths from {start} to {end}:")
paths = find_paths(network, start, end)
for path in paths:
print(" -> ".join(path))
虽然DFS深入图中，但BFS在移动到下一层之前会探索一个节点的所有邻居。每个都有其优势：DFS使用更少的内存，并且可以在不探索所有节点的情况下找到路径；BFS保证在无权重图中找到最短路径。