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

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 在 Python 编程中,掌握图的深度优先遍历(DFS)和广度优先遍历(BFS)是进阶的关键。这两种算法不仅理论重要,还能解决实际问题。本文介绍了图的基本概念、邻接表表示方法,并给出了 DFS 和 BFS 的 Python 实现代码示例,帮助读者深入理解并应用这些算法。

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 大神!

相关文章
|
1月前
|
测试技术 开发者 Python
深入浅出:Python中的装饰器解析与应用###
【10月更文挑战第22天】 本文将带你走进Python装饰器的世界,揭示其背后的魔法。我们将一起探索装饰器的定义、工作原理、常见用法以及如何自定义装饰器,让你的代码更加简洁高效。无论你是Python新手还是有一定经验的开发者,相信这篇文章都能为你带来新的启发和收获。 ###
23 1
|
1月前
|
设计模式 测试技术 开发者
Python中的装饰器深度解析
【10月更文挑战第24天】在Python的世界中,装饰器是那些能够为函数或类“添彩”的魔法工具。本文将带你深入理解装饰器的概念、工作原理以及如何自定义装饰器,让你的代码更加优雅和高效。
|
6月前
|
XML JavaScript 关系型数据库
Python XML 解析
Python XML 解析
|
7月前
|
XML JavaScript API
Python XML 解析
Python XML 解析
|
XML JavaScript 关系型数据库
|
7月前
|
XML JavaScript API
「Python系列」Python XML解析
在Python中,解析XML文件通常使用内置的`xml.etree.ElementTree`模块,它提供了一个轻量级、高效的方式来解析XML文档。此外,还有其他的第三方库,如`lxml`和`xml.dom`,它们提供了更多的功能和灵活性。
73 0
|
7月前
|
XML 安全 API
Python读写XML文件:深入解析与技术实现
Python读写XML文件:深入解析与技术实现
229 0
|
XML JSON 编解码
|
XML 关系型数据库 数据格式
|
XML 数据格式 Python