当前位置：首页 > news >正文

数据结构与算法Python版图的应用与广度优先搜索

news 来源：原创 2025/7/19 20:20:30

文章目录

一、图的应用-词梯问题
二、图的广度优先搜索

一、图的应用-词梯问题

词梯问题 Word Ladder

从一个单词演变到另一个单词，其中的过程可以经过多个中间单词。要求是相邻两个单词之间差异只能是1个字母
如FOOL变SAGE：FOOL >> POOL >> POLL >> POLE >> PALE >>SALE >> SAGE
采用图来解决这个问题，我们的目标是找到最短的单词变换序列
- 将可能的单词之间的演变关系表达为图
- 采用“广度优先搜索 BFS”，来搜寻从开始单词到结束单词之间的所有有效路径
- 选择其中最快到达目标单词的路径

构建单词关系图

将单词作为顶点的标识Key，如果两个单词之间仅相差1个字母，就在它们之间设一条边
使用无向图，边没有权重
算法一：将所有单词作为顶点加入图中，对每个顶点（单词），与其它所有单词进行比较，如果相差仅1个字母，则建立一条边。时间复杂度是O(n^2)
算法二：将所有单词作为顶点加入图中，对于有N个字母的单词，建立N个桶，每个桶可以存放若干单词。单词的其中一个字母使用_通配符，所有匹配的单词放到同一桶中。最后，在同一个桶的单词之间建立边。

在这里插入图片描述

单词文件words.txt的内容如下：

fool
cool
pool
poll
pole
pall
fall
fail
foil
foul
pale
page
sage
pope
sale

构建单词关系图

def build_graph(word_file):"""构建单词关系图"""buckets = {}g = Graph()path = Path(word_file)contents = path.read_text()words = contents.splitlines()# 建立桶for word in words:for i in range(len(word)):bucket_key = word[:i] + "_" + word[i + 1 :]# 如果key存在，则把单词加入到桶的列表；否则，创建桶和桶列表的第一个单词if bucket_key in buckets:buckets[bucket_key].append(word)else:buckets[bucket_key] = [word]# 建立边for bucket_key in buckets.keys():for word1 in buckets[bucket_key]:for word2 in buckets[bucket_key]:if word1 != word2:g.add_edge(word1, word2)return gword_file = "words.txt"
word_graph = build_graph(word_file)
for values in word_graph.vertexes.values():print(values)### 输出结果
fool connected to : ['cool', 'pool', 'foil', 'foul']
cool connected to : ['fool', 'pool']
pool connected to : ['fool', 'cool', 'poll']        
foil connected to : ['fool', 'foul', 'fail']        
foul connected to : ['fool', 'foil']
poll connected to : ['pool', 'pall', 'pole']        
pall connected to : ['poll', 'fall', 'pale']        
pole connected to : ['poll', 'pale', 'pope']        
pale connected to : ['pole', 'pall', 'sale', 'page']
pope connected to : ['pole']
fall connected to : ['pall', 'fail']
fail connected to : ['fall', 'foil']
sale connected to : ['pale', 'sage']
page connected to : ['pale', 'sage']
sage connected to : ['page', 'sale']

二、图的广度优先搜索

广度优先搜索 Breadth First Search

给定图G，以及开始搜索的起始顶点s，搜索所有从顶点s可到达顶点的边。在达到更远的距离k+1的顶点之前，找到全部距离为k的顶点
就像构建一棵树的过程，从顶部向下逐步增加层次。在增加层次之前，添加了所有兄弟节点到树中

广度优先搜索-算法过程

为了跟踪顶点的加入过程，并避免重复顶点，为顶点增加3个属性
- 距离distance：从起始顶点到此顶点路径长度；
- 前驱顶点predecessor：可反向追溯到起点；
- 颜色color：标识了此顶点是尚未发现（白色）、已经发现（灰色）、还是已经完成探索（黑色）
为决定下一个要探索的顶点，用一个队列Queue来对已发现的顶点进行排列
从起始顶点s开始，作为刚发现的顶点，标注为灰色，距离为0，前驱为None，加入队列，接下来是个循环迭代过程：
- 从队首取出一个顶点作为当前顶点；
- 遍历当前顶点的邻接顶点，如果是尚未发现的白色顶点，则将其颜色改为灰色（已发现），距离增加1，前驱顶点为当前顶点，加入到队列中
- 遍历完成后，将当前顶点设置为黑色（已探索过），循环回到步骤1的队首取当前顶点

更新后的顶点类和图类

class Vertex:"""顶点类"""def __init__(self, key, distance=0, pred=None, color="white"):self.key = keyself.connected_to = {}self.distance = distanceself.pred = predself.color = colordef __str__(self):return f"{self.key} connected to : {[x.key for x in self.connected_to]}"def add_neighbor(self, nbr, weight=0):"""键为nbr顶点对象，值为权重"""self.connected_to[nbr] = weightdef get_connections(self):return self.connected_to.keys()def get_key(self):return self.keydef get_weight(self, nbr):return self.connected_to.get(nbr, None)def set_distance(self, distance):self.distance = distancedef get_distance(self):return self.distancedef set_pred(self, pred):self.pred = preddef get_pred(self):return self.preddef set_color(self, color):self.color = colordef get_color(self):return self.colorclass Graph:"""图"""def __init__(self):self.vertexes = {}self.num_vertexes = 0def __contains__(self, key):return key in self.vertexesdef __iter__(self):return iter(self.vertexes.values())def add_vertex(self, key):"""加入顶点：以key为键，以Vertex对象为值"""self.num_vertexes += 1new_vertex = Vertex(key)self.vertexes[key] = new_vertexreturn new_vertexdef get_vertex(self, key):if key in self.vertexes:return self.vertexes[key]else:return Nonedef add_edge(self, begin, end, cost=0):"""添加边，如果顶点不存在，先添加顶点再加边"""if begin not in self.vertexes:self.add_vertex(begin)if end not in self.vertexes:self.add_vertex(end)self.vertexes[begin].add_neighbor(self.vertexes[end], cost)def get_vertexes(self):"""返回所有顶点"""return self.vertexes.keys()def get_edge_count(self):count = 0for i in self.vertexes.values():count += len(i.connected_to)return count

广度优先搜索-算法实现

from pathlib import Path
from my_queue import Queuedef bfs(graph: Graph, start_word):"""广度优先搜索：以start_word为起点，遍历其它顶点，并为每个顶点着色、赋距离和前驱"""start = graph.get_vertex(start_word)start.set_distance(0)start.set_pred(None)v_queue = Queue()v_queue.enqueue(start)while v_queue.size() > 0:current_vert: Vertex = v_queue.dequeue()for nbr in current_vert.get_connections():if nbr.get_color() == "white":nbr.set_color("gray")nbr.set_distance(current_vert.get_distance() + 1)nbr.set_pred(current_vert)v_queue.enqueue(nbr)current_vert.set_color("black")

词梯问题求解

def traverse(graph: Graph, target_word):"""输出目标单词的路径，即词梯问题的解"""target = graph.get_vertex(target_word)x = targetwhile x.get_pred() != None:print(x.get_key())x = x.get_pred()print(x.get_key())word_file = "words.txt"
word_graph = build_graph(word_file)
bfs(word_graph, "fool")
traverse(word_graph, "sage")### 输出结果
sage
sale
pale
pall
poll
pool
fool

广度优先搜索BFS- 算法分析

广度优先搜索算法主体是两个循环的嵌套。while循环对每个顶点访问一次，所以是O(|V|)；嵌套在while中的for，由于每条边只有在其起始顶点u出队的时候才会被检查一次，所以边最多被检查1次，一共是O(|E|)。综合起来BFS的时间复杂度为O(|V|+|E|)
建立BFS树之后，回溯顶点到起始顶点的过程最差情况为O(|V|)；创建单词关系图最差情况为O(|V|2)。

您正在阅读的是《数据结构与算法Python版》专栏！关注不迷路~

数据结构与算法Python版图的应用与广度优先搜索

文章目录一、图的应用-词梯问题二、图的广度优先搜索一、图的应用-词梯问题词梯问题 Word Ladder 从一个单词演变到另一个单词，其中的过程可以经过多个中间单词。要求是相邻两个单词之间差异只能是1个字母如FOOL变SAGE：FOOL >> POOL >>…...

编程日记 2025/7/19 20:20:30

Unity——InputField组件自动换行和enter键换行

文章目录输入框实现换行功能输入框实现换行功能在Unity中，如果你想要在输入框（如InputField）中实现换行功能 ，你需要确保以下几点： 1、文本组件支持多行： 确保你的InputField的文本组件（Te…...

编程日记 2025/7/20 8:55:21

1.环境要求:jdk11以上 2.下载wget https://dlcdn.apache.org/solr/solr/9.7.0/solr-9.7.0.tgz 3.解压 4.修改solr.in.sh配置 5.启动命令 bin/solr start 6.创建core bin/solr create -c <core名称> 注意:用solr ui界面创建，会提示找不到solrconfig.xml和m…...

编程日记 2025/7/14 21:55:35

虚幻引擎UE5渲染不够快的解决办法

虚幻引擎是由Epic Games公司开发的一款功能强大、全球最开放且先进的实时 3D 创作工具，广泛应用于游戏、影视、建筑可视化、虚拟现实等多个领域！虚幻引擎UE5如何实现在网上极速渲染呢？本文提供云渲染和云电脑两套方案用于渲染提速&#xff…...

编程日记 2025/7/18 9:29:13

基于STM32的智能家居环境监控系统设计

目录引言系统设计硬件设计软件设计系统功能模块环境监控模块控制模块显示模块系统实现硬件实现软件实现系统调试与优化结论与展望 1. 引言随着智能家居技术的发展，环境监控系统已经成为家居管理的重要组成部分。智能家居环境监控系统通过实时监测室内温度、湿…...

编程日记 2025/7/20 8:50:06

Android service framework笔记

1. 网络摘录如何添加一个Application Framework Service（一）（without native code）如何添加一个Application Framework Service（二）（with native code） 2.书籍摘录...

编程日记 2025/7/20 8:44:34

【图像处理lec10】图像压缩

目录一、图像压缩基础 1、图像压缩的基本概念 2、数据冗余与压缩比 3、三种主要的数据冗余类型 4、保真度评估标准（Fidelity Criteria） 5、应用与实践二、图像压缩模型 1、图像压缩模型概述 （1）压缩系统的结构 &#…...

编程日记 2025/7/19 20:25:44

flask后端开发（2）：URL与视图

目录 URL定义request获取请求参数 gitcode地址： https://gitcode.com/qq_43920838/flask_project.git URL定义 from flask import FlaskappFlask(__name__)app.route(/) def hello_world():return Hello World!app.route(/profile) def profile():return 我是个人…...

编程日记 2025/7/15 17:45:12

Linux Ubuntu24配置安装Java

目录一. 通过apt安装java1.1 列出所有可用java版本1.2 安装指定java版本1.3 安装后确认1.4 /etc/alternatives/目录二. 手动安装java 一. 通过apt安装java 1.1 列出所有可用java版本 apt list openjdk-*jdk apluserubuntu24-01:~$ apt list openjdk-*jdk Listing... Done …...

编程日记 2025/7/19 22:54:25

线段树例题题解

卫星覆盖（NOI1997） 题面： SERCOI（Space-Earth Resource Cover-Observe lnstitute） 是一个致力于利用卫星技术对空间和地球资源进行覆盖观测的组织。现在他们研制成功一种新型资源观测卫星 -SERCOI-308。这种卫星可以…...

编程日记 2025/7/20 9:02:25

极品飞车6的游戏手柄设置

极品飞车，既可以用键盘来控制车辆的前进、后退、左转、右转、加速与减速，也可以使用游戏手柄来操作车辆的运行。需要注意的是，极品飞车虽然支持手柄，但是仅支持常见的北通、罗技还有部分Xbox系列的手柄，至于其他的PS4手…...

编程日记 2025/7/17 19:57:04

为何DeepSeek V3模型为自己是ChatGPT？

DeepSeek V3 AI模型：为何它认为自己是ChatGPT？ 引言在人工智能领域，最新的技术进展总是令人兴奋。最近，一家资金雄厚的中国AI实验室DeepSeek发布了一款新的AI模型——DeepSeek V3，它在多个流行基准测试中超越了许多…...

编程日记 2025/7/15 21:35:48

【每日学点鸿蒙知识】人脸活体检测、NodeController刷新、自动关闭输入框、Row设置中间最大宽、WebView单例

1、HarmonyOS 人脸活体检测调用？ H5调用应用侧方法可参考以下demo： index.ets Web()//注册方法.javaScriptProxy({object: this.testObj,name: "testObjName",methodList: ["getLocationTS"],controller: this.webController})cla…...

编程日记 2025/7/16 5:27:48

深入理解Composer自动加载机制

Composer是PHP生态系统中最常用的依赖管理工具之一，它不仅能够帮助开发者管理项目的依赖关系，还能够自动加载这些依赖项。自动加载机制是Composer的核心功能之一，通过自动加载，开发者可以在运行时按需加载所需的类和文件&#xff…...

编程日记 2025/7/17 18:58:54

SQL SERVER日常运维巡检系列之-日志

前言做好日常巡检是数据库管理和维护的重要步骤，而且需要对每次巡检日期、结果进行登记，同时可能需要出一份巡检报告。本系列旨在解决一些常见的困扰： 不知道巡检哪些东西不知道怎么样便捷体检机器太多体检麻烦生成报告困难，无…...

编程日记 2025/7/14 14:40:18

2024年中国新能源汽车用车发展怎么样 PaperGPT（二）

用车趋势深入分析接上文，2024年中国新能源汽车用车发展怎么样 PaperGPT（一）-CSDN博客本文将继续深入探讨新能源汽车的用车强度、充电行为以及充电设施的现状。用车强度月均行驶里程：2024年纯电车辆月均行驶超过1500公里&…...

编程日记 2025/7/18 10:19:01

【数据结构】线性数据结构——链表

1. 定义链表是一种线性数据结构，由多个节点（Node）组成。每个节点存储数据和指向下一个节点的指针。与数组不同，链表的节点不需要在内存中连续存储。 2. 特点动态存储： 链表的大小不固定，可以动态增加或…...

编程日记 2025/7/20 1:30:18

Spring中的设计模式

Spring中的设计模式控制反转(IoC)和依赖注入(DI) IoC 是一个原则，而不是一个模式，以下模式（但不限于）实现了 IoC 原则。 **Spring IoC 容器就像是一个工厂一样，当我们需要创建一个对象的时候，只需要配置…...

编程日记 2025/7/19 9:02:41

微信小程序给外面的view设置display:flex；后为什么无法给里面的view设置宽度

如果父盒子view设置了display:flex，子view设置宽度值无效，宽度值都是随着内容多少而改变： 问题视图： 原因： flex布局元素的子元素，自动获得了flex-shrink的属性解决方法： 给子view增加:fl…...

编程日记 2025/7/18 5:48:11

异步爬虫之aiohttp的使用

在上一篇博客我们介绍了异步爬虫的基本原理和 asyncio 的基本用法，并且在最后简单提及了使用aiohttp 实现网页爬取的过程。本篇博客我们介绍一下 aiohttp 的常见用法。基本介绍前面介绍的 asyncio模块，其内部实现了对 TCP、UDP、SSL协议的异步操作&a…...

编程日记 2025/7/17 16:55:28

vue3大屏实现；使用使用CSS Grid实现大屏

文章目录一、效果1.效果2.使用CSS Grid3.插件4.html代码5.index.scss代码一、效果 1.效果方案：采用CSS的Grid布局，实现首页大屏模块划分和自适应功能； 布局： 大屏主要内容，高宽比是1920*1080；即16:9的…...

编程日记 2025/7/19 19:48:35

安卓入门二 Kotlin基础

Kotlin Kotlin的历史 Kotlin由Jet Brains公司开发设计，2011年公布第一版，2012年开源。 2016年发布1.0正式版，并且Jet Brains在IDEA加入对Kotlin的支持，安卓自此又有新的选择。 2019年谷歌宣布Kotlin成为安卓第一开发语言&#x…...

编程日记 2025/7/18 5:15:01

在ubuntu上如何使用sdkman安装两个版本的java并进行管理和维护

在Ubuntu上使用SDKMAN安装和管理两个不同版本的Java的步骤如下： 安装SDKMAN 打开终端，使用以下命令安装SDKMAN： curl -s "https://get.sdkman.io" | bash这个命令会下载并运行SDKMAN!的安装脚本。安装完成后，需要打开…...

编程日记 2025/7/15 22:18:54

《代码随想录》Day20打卡！

《代码随想录》二叉树：二叉搜索树的最近公共祖先本题的完整题目如下： 本题的思路如下： 1.之前写过一个二叉树的最近公共祖先，本题相比于另一道题，不同是本题是二叉搜索树，有一些可用的性质。 2.本题使用递…...

编程日记 2025/7/14 11:39:21

GPIO相关寄存器，点灯

目录一.输入模式 1.浮空输入 2.上拉输入 3.下拉输入 4.模拟输入二.输出模式 1.推挽输出 2.开漏输出三.寄存器 1.寄存器的作用 2.功能与类型 3.控制某一引脚输出电压来点灯所需要控制的寄存器 1.打开对应时钟开关 2.端口模式寄存器 ---输出模式 3.输出类型寄存…...

编程日记 2025/7/17 1:26:39

25 - GRACE Mascon数据缺失月份数据插值

25 - GRACE Mascon数据缺失月份数据插值 0 引言1 程序包获取1.1 获取ssa插值算法程序包1.2 try2 利用ssa对grace mascon数据进行插值3 完整代码及相关函数3.1 Main程序3.1 子程序4 总结0 引言 💦💦💦💦💦 上篇介绍了grace mascon数据提取及简单的分析过程，仔细…...

编程日记 2025/7/15 9:08:04

深入理解Redis：从理论到实践的Java之旅

Redis，这个开源的内存数据结构存储系统，自2009年诞生以来，凭借其丰富的数据结构、快速的读写性能以及高度的可扩展性，迅速成为了分布式系统和高并发应用中的明星组件。本文将带你深入理解Redis，并通过Java语言的实践示…...

编程日记 2025/7/13 11:22:48

REDIS的集群

REDIS的集群模式： 主从模式：redis高可用的基础，哨兵和集群都是建立在此基础之上特点： 主从模式和数据库的主从模式（工作模式）是一样的，主负责写入，然后把写入到数据同步到从&…...

编程日记 2025/7/19 14:44:09

linux——vi命令常用操作

一、vi模式 vi一般分为三种模式，分别是命令行模式、插入模式、末行模式 1.命令模式：控制屏幕光标的移动，按 ：进入末行模式，按 i（其他插入命令也可） 进入插入模式； 2.插入模式&…...

编程日记 2025/7/18 20:49:10

SKETCHPAD——允许语言模型生成中间草图,在几何、函数、图算法和游戏策略等所有数学任务中持续提高基础模型的性能

概述论文地址：https://arxiv.org/pdf/2406.09403 素描是一种应用广泛的有效工具，包括产生创意和解决问题。由于素描能直接传达无法用语言表达的视觉和空间信息，因此从古代岩画到现代建筑图纸，素描在世界各地被用于各种用途。儿童…...

编程日记 2025/7/16 13:45:21

计算机网络•自顶向下方法：网络应用原理

网络应用原理网络应用架构目前有两种主流的网络应用架构： 客户-服务器架构（Client-server） 服务器（server）: 有一台总是在线的主机，上面运行着服务器程序(server)服务器主机(server machine)具有永久的…...

编程日记 2025/7/19 19:08:23

python: Oracle Stored Procedure query table

oracel sql script CREATE OR REPLACE PROCEDURE SelectSchool(paramSchoolId IN char,p_cursor OUT SYS_REFCURSOR ) AS BEGINOPEN p_cursor FORSELECT *FROM SchoolWHERE SchoolId paramSchoolId; END SelectSchool; /-- 查询所有 CREATE OR REPLACE PROCEDURE SelectScho…...

编程日记 2025/7/14 20:13:56

文章目录

一、图的应用-词梯问题

二、图的广度优先搜索

相关文章：