深度优先遍历经典例题

有向

的

（Depth First Search, DFS）是一种用于遍历

的

。它从

中的一个顶点开始，沿着一条路径尽可能深地访问

中的顶点，直到无法继续前进为止，然后回溯到前一个顶点，继续探索其他路径。以下是一个用Python实现有向

的示例代码：

 # 定义有向 图 类 class DirectedGraph: def __init__(self): self.graph = {}  # 添加边 def add_edge(self, start, end): if start in self.graph: self.graph[start].append(end) else: self.graph[start] = [end]  # 深度优先遍历 def dfs(self, start): visited = set() # 记录已访问的节点  def dfs_helper(node): visited.add(node) print(node, end=" ") # 输出节点值  if node in self.graph: for neighbor in self.graph[node]: if neighbor not in visited: dfs_helper(neighbor)  dfs_helper(start)  # 创建有向 图 对象 graph = DirectedGraph()  # 添加边 graph.add_edge('A', 'B') graph.add_edge('A', 'C') graph.add_edge('B', 'D') graph.add_edge('B', 'E') graph.add_edge('C', 'F')  # 深度优先遍历 print(" 深度优先遍历 结果：") graph.dfs('A') 

运行以上代码，输出结果为：A B D E C F

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/10131.html