博客

python数据结构之图深度优先和广度优先实例详解

  • Post category:Python

下面是详细讲解“Python数据结构之图深度优先和广度优先实例详解”的完整攻略。

1. 什么是图？

图是由节点和边组成的一种数据结构。节点表示图中的元素，边表示之间的关系。图可以用来表示各种实际问题，如社交网络、地图等。

2. Python实现图的深度先和广度优先遍历

2.1 深度优先遍历

下面是Python实现图的深度优先遍历的示例：

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)

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 广度优先遍历

下面是Python实现图的广度优先遍历示例：

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

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

输出结果为： B C D E F

3. 总结

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

Tags: ,