跨境派

跨境派

跨境派,专注跨境行业新闻资讯、跨境电商知识分享!

当前位置:首页 > 工具系统 > 防关联工具 > Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

时间:2024-04-20 07:55:26 来源:网络cs 作者:言安琪 栏目:防关联工具 阅读:

标签: 优先  广度  深度  基础 

Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

引言 1. 深度优先搜索( DFS )算法概述2. 深度优先搜索( DFS )算法实现实例1:图的 DFS 遍历实例2:二叉树的 DFS 遍历 3. 广度优先搜索( BFS )算法概述4. 广度优先搜索( BFS )算法实现实例1:图的 BFS 遍历实例2:二叉树的 BFS 遍历 5. DFS 与 BFS 的对比总结

引言

深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFSBFS 算法的基本概念,并通过实例代码演示它们的应用。

😃😄 ❤️ ❤️ ❤️

1. 深度优先搜索( DFS )算法概述

深度优先搜索( DFS )是一种用于遍历或搜索图或树的算法,它从起始节点开始,沿着一条路径一直深入直到无法继续为止,然后回溯到上一个节点继续探索。 DFS 使用栈来记录遍历的路径,它优先访问最近添加到栈的节点。

DFS 的主要优点是简单且易于实现,它不需要额外的数据结构来记录节点的访问情况,仅使用栈来存储遍历路径。然而, DFS 可能会陷入无限循环中,因为它不考虑节点是否已经访问过。

2. 深度优先搜索( DFS )算法实现

实例1:图的 DFS 遍历

# 图的DFS遍历def dfs(graph, start, visited):    # 访问当前节点    print(start, end=' ')    # 标记当前节点为已访问    visited[start] = True    # 遍历当前节点的邻居节点    for neighbor in graph[start]:        # 如果邻居节点未被访问,则继续深度优先搜索        if not visited[neighbor]:            dfs(graph, neighbor, visited)# 图的邻接表表示graph = {    'A': ['B', 'C'],    'B': ['A', 'D', 'E'],    'C': ['A', 'F', 'G'],    'D': ['B'],    'E': ['B'],    'F': ['C'],    'G': ['C']}# 标记节点是否已访问的列表visited = {node: False for node in graph}# 从节点A开始进行DFS遍历print("DFS遍历结果:")dfs(graph, 'A', visited)

代码解释:上述代码演示了使用 DFS 算法遍历图的实例。我们使用邻接表表示图,然后从节点 A 开始进行 DFS 遍历。 DFS 算法通过递归的方式深入遍历每个节点,并使用 visited 字典记录节点是否已经访问过,防止重复访问。

实例2:二叉树的 DFS 遍历

# 二叉树节点定义class TreeNode:    def __init__(self, val):        self.val = val        self.left = None        self.right = None# 二叉树的DFS遍历def dfs_binary_tree(root):    if root is None:        return    print(root.val, end=' ')    dfs_binary_tree(root.left)    dfs_binary_tree(root.right)# 构造二叉树root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)# 二叉树的DFS遍历print("二叉树的DFS遍历结果:")dfs_binary_tree(root)

代码解释:上述代码演示了使用 DFS 算法遍历二叉树的实例。我们构造了一个二叉树,并使用递归的方式进行 DFS 遍历。 DFS 算法沿着左子树一直深入到底,然后再回溯遍历右子树。

3. 广度优先搜索( BFS )算法概述

广度优先搜索( BFS )是一种用于遍历或搜索图或树的算法,它从起始节点开始,逐层地向外扩展,先访问当前节点的所有邻居节点,然后再访问邻居节点的邻居节点,直到遍历完所有节点。

BFS 使用队列来记录遍历的路径,它优先访问最早添加到队列的节点。 BFS 的主要优点是能够找到起始节点到目标节点的最短路径,因为它是逐层遍历的。

4. 广度优先搜索( BFS )算法实现

实例1:图的 BFS 遍历

from collections import deque# 图的BFS遍历def bfs(graph, start):    # 使用队列来记录遍历路径    queue = deque([start])    # 标记节点是否已访问的集合    visited = set([start])    while queue:        node = queue.popleft()        print(node, end=' ')        for neighbor in graph[node]:            if neighbor not in visited:                queue.append(neighbor)                visited.add(neighbor)# 图的邻接表表示graph = {    'A': ['B', 'C'],    'B': ['A', 'D', 'E'],    'C': ['A', 'F', 'G'],    'D': ['B'],    'E': ['B'],    'F': ['C'],    'G': ['C']}# 从节点A开始进行BFS遍历print("BFS遍历结果:")bfs(graph, 'A')

代码解释:上述代码演示了使用 BFS 算法遍历图的实例。我们使用邻接表表示图,然后从节点 A 开始进行 BFS 遍历。 BFS 算法通过使用队列来逐层遍历图的节点,并使用 visited 集合记录节点是否已经访问过,防止重复访问。

实例2:二叉树的 BFS 遍历

from collections import deque# 二叉树节点定义class TreeNode:    def __init__(self, val):        self.val = val        self.left = None        self.right = None# 二叉树的BFS遍历def bfs_binary_tree(root):    if root is None:        return    queue = deque([root])    while queue:        node = queue.popleft()        print(node.val, end=' ')        if node.left:            queue.append(node.left)        if node.right:            queue.append(node.right)# 构造二叉树root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)# 二叉树的BFS遍历print("二叉树的BFS遍历结果:")bfs_binary_tree(root)

代码解释:上述代码演示了使用 BFS 算法遍历二叉树的实例。我们构造了一个二叉树,并使用队列来逐层遍历二叉树的节点。 BFS 算法先访问根节点,然后依次将左子节点和右子节点添加到队列中,再逐层遍历子树。

5. DFS 与 BFS 的对比

DFSBFS 是两种不同的图遍历算法,在不同的应用场景下具有不同的优势:

DFS 适用于找到起始节点到目标节点的路径,但不一定是最短路径。它通过递归的方式深入探索图的分支,因此对于深度较小的图或树, DFS 通常表现较好。

BFS 适用于找到起始节点到目标节点的最短路径。它通过逐层遍历图的节点,从而保证找到的路径是最短的。在需要寻找最短路径的情况下, BFS 是更好的选择。

总结

本篇博客介绍了深度优先搜索( DFS )和广度优先搜索( BFS )算法的基本概念,并通过实例代码演示了它们在图和二叉树遍历中的应用。

DFS 是一种深入探索图或树的算法,通过递归方式遍历每个节点,优先访问最近添加到栈的节点。 BFS 是一种逐层遍历图或树的算法,通过队列来存储遍历路径,优先访问最早添加到队列的节点。

[ 专栏推荐 ]
😃 《Python 算法初阶:入门篇》😄
❤️【简介】:本课程是针对 Python 初学者设计的算法基础入门课程,涵盖算法概念、时间复杂度、空间复杂度等基础知识。通过实例演示线性搜索、二分搜索等算法,并介绍哈希表、深度优先搜索、广度优先搜索等搜索算法。此课程将为学员提供扎实的 Python 编程基础与算法入门,为解决实际问题打下坚实基础。

在这里插入图片描述

本文链接:https://www.kjpai.cn/news/2024-04-20/160503.html,文章来源:网络cs,作者:言安琪,版权归作者所有,如需转载请注明来源和作者,否则将追究法律责任!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。

文章评论