Python 大神修炼手册:图的深度优先&广度优先遍历,深入骨髓的解析

简介: 【7月更文挑战第12天】Python进阶必学:DFS和BFS图遍历算法。理解图概念,用邻接表建无向图,实现DFS和BFS。DFS适用于查找路径,BFS解决最短路径。通过实例代码加深理解,提升编程技能。

Python 编程的进阶之路上,掌握图的深度优先遍历(Depth-First Search,简称 DFS)和广度优先遍历(Breadth-First Search,简称 BFS)是至关重要的一步。这两种遍历算法不仅在理论上具有重要意义,在实际应用中也能解决许多复杂的问题。接下来,让我们一起深入学习这两种算法。

首先,我们来了解一下图的基本概念。图由顶点(Vertex)和边(Edge)组成,可以分为有向图和无向图。为了在 Python 中表示图,我们可以使用邻接表或者邻接矩阵的方式。

下面是使用邻接表表示无向图的 Python 代码示例:

class Graph:
    def __init__(self):
        self.graph = {
   }

    def add_edge(self, u, v):
        if u in self.graph:
            self.graph[u].append(v)
        else:
            self.graph[u] = [v]

        if v in self.graph:
            self.graph[v].append(u)
        else:
            self.graph[v] = [u]

有了图的表示,接下来实现 DFS 算法。

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

为了更好地理解 DFS,假设我们有一个简单的图,顶点为 1 到 5,边为 (1, 2), (1, 3), (2, 4), (2, 5) 。

g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)

print("DFS 遍历:")
dfs(g.graph, 1)

接下来是 BFS 算法的实现。

from collections import deque

def bfs(graph, start):
    visited = {
   start}
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        print(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

同样对于上述的图,进行 BFS 遍历:

print("BFS 遍历:")
bfs(g.graph, 1)

在实际应用中,DFS 常用于查找路径、判断图是否连通等问题。而 BFS 则常用于求最短路径、层次遍历等情况。

通过以上的详细讲解和示例代码,相信您对图的 DFS 和 BFS 遍历有了更深入的理解。不断地练习和应用这些知识,您将在 Python 编程的道路上更上一层楼,逐渐成为 Python 大神!

相关文章
|
6天前
|
存储 大数据 Unix
Python生成器 vs 迭代器:从内存到代码的深度解析
在Python中,处理大数据或无限序列时,迭代器与生成器可避免内存溢出。迭代器通过`__iter__`和`__next__`手动实现,控制灵活;生成器用`yield`自动实现,代码简洁、内存高效。生成器适合大文件读取、惰性计算等场景,是性能优化的关键工具。
72 2
|
12天前
|
机器学习/深度学习 文字识别 Java
Python实现PDF图片OCR识别:从原理到实战的全流程解析
本文详解2025年Python实现扫描PDF文本提取的四大OCR方案(Tesseract、EasyOCR、PaddleOCR、OCRmyPDF),涵盖环境配置、图像预处理、核心识别与性能优化,结合财务票据、古籍数字化等实战场景,助力高效构建自动化文档处理系统。
170 0
|
12天前
|
机器学习/深度学习 JSON Java
Java调用Python的5种实用方案:从简单到进阶的全场景解析
在机器学习与大数据融合背景下,Java与Python协同开发成为企业常见需求。本文通过真实案例解析5种主流调用方案,涵盖脚本调用到微服务架构,助力开发者根据业务场景选择最优方案,提升开发效率与系统性能。
144 0
机器学习/深度学习 算法 自动驾驶
116 0
|
20天前
|
算法 安全 数据安全/隐私保护
Python随机数函数全解析:5个核心工具的实战指南
Python的random模块不仅包含基础的随机数生成函数,还提供了如randint()、choice()、shuffle()和sample()等实用工具,适用于游戏开发、密码学、统计模拟等多个领域。本文深入解析这些函数的用法、底层原理及最佳实践,帮助开发者高效利用随机数,提升代码质量与安全性。
98 0
|
25天前
|
数据可视化 Linux iOS开发
Python脚本转EXE文件实战指南:从原理到操作全解析
本教程详解如何将Python脚本打包为EXE文件,涵盖PyInstaller、auto-py-to-exe和cx_Freeze三种工具,包含实战案例与常见问题解决方案,助你轻松发布独立运行的Python程序。
317 2
|
27天前
|
设计模式 缓存 运维
Python装饰器实战场景解析:从原理到应用的10个经典案例
Python装饰器是函数式编程的精华,通过10个实战场景,从日志记录、权限验证到插件系统,全面解析其应用。掌握装饰器,让代码更优雅、灵活,提升开发效率。
87 0
|
数据可视化 Python 数据挖掘
《数据科学实战手册(R+Python)》一导读
本书提供了多种令读者能够学习如何从数据创造价值的机会。书中所用的数据来自很多不同的项目,而这些项目可以体现出最新的数据科学项目的各种维度。每一章的内容都是独立的,包含了电脑屏幕截图、代码片段、必要的详细解释。我们对处理数据的过程和实际应用特别关注。这些内容都是以循序渐进的方式来安排写作的。
1352 0
|
12天前
|
数据采集 机器学习/深度学习 人工智能
Python:现代编程的首选语言
Python:现代编程的首选语言
184 102
|
12天前
|
数据采集 机器学习/深度学习 算法框架/工具
Python:现代编程的瑞士军刀
Python:现代编程的瑞士军刀
182 104

推荐镜像

更多