博客

Python实现深度遍历和广度遍历的方法

  • Post category:Python

下面是详细讲解“Python实现深度遍历和广度遍历的方法”的完整攻略。

1. 什么是深度遍历和广度遍历？

深度遍历和广度遍历是图遍历中两种常用的方法。深度遍历是指从某个节点开始，沿着一条路径一直走到底，直到不能再走为止，然后回溯到上一个节点，继续走其他路径，直到遍历完整个图。广度遍历是指从某个节点开始，先遍该节点的所有邻居节点，然后再遍历邻居节点的邻居节点，直到遍历完整个图。

2. Python实现深度遍历和广度遍历的方法

下面是Python实现深度遍历和广度遍历的方法的示例：

2.1 深度遍历

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next_node in graph[start] - visited:
        dfs(graph, next_node, visited)
    return visited

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

dfs(graph, 'A')

上述代码中，定义了一个函数dfs，用于实现深度遍历。首先定义一个集合visited，用存储已经访问过的节点。然后将起始节点start加入visited集合中，并使用print函数输出该节点。遍历该节点的所有邻居节点，如果邻居节点没有被访问过，则递归调用dfs函数，继续遍历邻居节点。最后返回visited集合。

定义一个图graph，使用dfs函数该图进行深度遍历，然后使用print函数输出结果。

输出结果为：A B D E F C

2.2 广度遍历

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node)
        for next_node in graph[node] - visited:
            visited.add(next_node)
            queue.append(next_node)

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

bfs(graph, 'A')

上述代码中，定义了一个函数bfs，用于实现广度遍历。首先定义一个集合，用于存储已经访问过的节点。然后定义一个队列queue，用于存储待访问的节点。将起始节点start加入visited集合和queue队列中。使用while循环，依次将队列中的节点出队，并使用print函数输出该节点。遍历该节点的所有邻居节点，如果邻居没有被访问过，则将其加入visited集合和queue队列中。最后返回visited集合。

定义一个图graph，使用bfs函数对该进行广度遍历，然后使用print函数输出结果。

输出结果为：A B C D E F

3. 总结

深度遍历和广度遍历是图遍历中两种常用的方法。在Python中可以使用递归和队列等数据结构实现深度遍历和广度遍历。深度遍历从某个节点开始，沿着一条路径一直走到底，直到不能再走为止，然后回溯到上一个节点，继续走其他路径，直到遍历完整个图。广度遍历从某个节点开始，先遍历该节点的所有邻居节点，然后再遍历邻居节点的邻居节点，直到遍历完整个图。

Tags: ,