python实现深度优先和广度优先搜索_python深度搜索和广度搜索

深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）是两种常见的图遍历算法，用于在图或树结构中搜索特定节点并解决问题。它们在解决不同类型的问题时具有不同的应用场景和性质。

深度优先搜索（DFS）：

深度优先搜索是一种通过尽可能深地搜索图的分支来找到目标节点的算法。该算法探索图中的一个分支，直到达到最深的节点，然后回溯到前一个节点，继续探索下一个分支，直到找到目标节点或无法继续搜索为止。DFS通常使用栈来跟踪待探索的节点。

基本思路：

• 从起始节点开始，将其标记为已访问并加入栈中。
• 弹出栈顶节点，查找它的未访问邻居节点。
• 对于每个未访问的邻居节点，标记为已访问，并将其压入栈中。
• 重复上述步骤，直到栈为空或找到目标节点。

DFS特点：

• DFS能够很快地进入图的深层，适合搜索目标较深的节点。
• 可能会陷入无限循环，因为它不记录已访问的节点。
• 使用递归实现的DFS易于理解，但在处理大型图时可能会导致堆栈溢出。

广度优先搜索（BFS）：

广度优先搜索是一种逐层遍历图的算法，它先探索图中所有距离起始节点为1个边的节点，然后是距离为2个边的节点，以此类推，直到找到目标节点或遍历完整个图。BFS通常使用队列来跟踪待探索的节点。

基本思路：

• 从起始节点开始，将其标记为已访问并加入队列中。
• 弹出队列头部节点，查找它的未访问邻居节点。
• 对于每个未访问的邻居节点，标记为已访问，并将其加入队列的尾部。
• 重复上述步骤，直到队列为空或找到目标节点。

BFS特点：

• BFS逐层遍历，先找到距离起始节点近的节点，适合寻找最短路径或最优解。
• 由于需要存储已访问的节点，内存消耗通常较大。
• 通常使用迭代实现，不易导致堆栈溢出。

应用场景：

• DFS：在解决路径问题时，可能需要使用DFS来找到所有可能的路径。它还适用于解决状态空间搜索和回溯问题。
• BFS：当需要找到最短路径或最短步骤来到达目标时，BFS是首选算法。它还用于拓扑排序和最小生成树等问题。

需要根据具体问题的特点选择DFS还是BFS算法。有时，结合两种算法的特点，使用深度优先搜索和广度优先搜索的变体，如迭代深化深度优先搜索（Iterative Deepening DFS）也是一种解决方法。

Python 实现1:

from collections import deque

def dfs_recursive(graph, current_node, target_node, visited):
    if current_node == target_node:
        return True

    visited[current_node] = True

    for neighbor in graph[current_node]:
        if not visited[neighbor]:
            if dfs_recursive(graph, neighbor, target_node, visited):
                return True

    return False


def bfs_iterative(graph, start_node, target_node):
    queue = deque([start_node])
    visited = {node: False for node in graph}
    visited[start_node] = True

    while queue:
        current_node = queue.popleft()
        if current_node == target_node:
            return True

        for neighbor in graph[current_node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

    return False

# 示例用法
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
visited = {node: False for node in graph}
start_node = 'A'
target_node = 'F'
result = dfs_recursive(graph, start_node, target_node, visited)
print(result)  # 输出：True（说明从节点A可以到达节点F）
start_node = 'A'
target_node = 'F'
result = bfs_iterative(graph, start_node, target_node)
print(result)  # 输出：True（说明从节点A可以到达节点F）


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

Python 实现2:

from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def DFS(root):
    if not root:
        return
    
    print(root.val)
    DFS(root.left)
    DFS(root.right)
    
def BFS(root):
    if not root:
        return
    
    queue = deque([root])
    
    while queue:
        cur = queue.popleft()
        print(cur.val)
        
        if cur.left:
            queue.append(cur.left)
        if cur.right:
            queue.append(cur.right)
            
root = Node('A') 
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.right.right = Node('E')

DFS(root) 
print("--------------")
BFS(root)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

DFS 和 BFS 在遍历树结构时有不同的应用场景,掌握两种算法的实现可以解决更多问题。