本文共 2481 字，大约阅读时间需要 8 分钟。
回溯法是一种选优搜索法，以达标为先，将不达标的路径及时回溯。结合图遍历，我们可以通过深度优先和广度优先两种算法实现对图结构的遍历。
class Graph(object): def __init__(self, *args, **kwargs): self.node_neighbors = {} self.visited = {} def add_nodes(self, nodelist): for node in nodelist: self.add_node(node) def add_node(self, node): if not node in self.nodes(): self.node_neighbors[node] = [] def add_edge(self, edge): u, v = edge if v not in self.node_neighbors[u] and u not in self.node_neighbors[v]: self.node_neighbors[u].append(v) if u != v: self.node_neighbors[v].append(u) def nodes(self): return self.node_neighbors.keys() def depth_first_search(self, root=None): order = [] def dfs(node): self.visited[node] = True order.append(node) for n in self.node_neighbors[node]: if not n in self.visited: dfs(n) if root: dfs(root) for node in self.nodes(): if not node in self.visited: dfs(node) print("深度优先顺序:", order) return order def breadth_first_search(self, root=None): queue = [] order = [] def bfs(): while len(queue) > 0: node = queue.pop(0) self.visited[node] = True for n in self.node_neighbors[node]: if not n in self.visited and not n in queue: queue.append(n) order.append(n) if root: queue.append(root) order.append(root) bfs() for node in self.nodes(): if not node in self.visited: queue.append(node) order.append(node) bfs() print("广度优先顺序:", order) return order# 初始化图结构g = Graph()g.add_nodes([i+1 for i in range(8)])g.add_edge((1, 2))g.add_edge((1, 3))g.add_edge((2, 4))g.add_edge((2, 5))g.add_edge((4, 8))g.add_edge((5, 8))g.add_edge((3, 6))g.add_edge((3, 7))g.add_edge((6, 7))# 测试nodes: [1, 2, 3, 4, 5, 6, 7, 8]广度优先顺序: [1, 2, 3, 4, 5, 6, 7, 8]深度优先顺序: [1, 2, 4, 8, 5, 3, 6, 7] 以上内容通过深度优先算法和广度优先算法实现了对图的遍历。代码中图的节点及边的建立，结合遍历算法，展示了不同遍历顺序的结果。
转载地址：http://zbymz.baihongyu.com/