本文共 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]

以上内容通过深度优先算法和广度优先算法实现了对图的遍历。代码中图的节点及边的建立，结合遍历算法，展示了不同遍历顺序的结果。