图的广度优先搜索遍历算法的分析与实现

图的遍历方式有深度与广度两种,既适合于无向图,也适合于有向图。通过具体示例,详细分析以邻接矩阵为存储结构图的广度优先搜索遍历算法,并在机器上实现完整的程序。

广度优先搜索算法在交叉立方体中的应用

给出了互连网络上的广度优先搜索算法，将其应用到交叉立方体上可以得到交叉立方体的广度优先生成树。连通图的广度优先生成树的树高不会超过该图其他同根生成树的高度。利用这一性质，通过分析交叉立方体的广度优先生成树的特征，给出了n维交叉立方体CQ_n的直径为「(n+1)／2」的另外一种证明方法；该算法可以用来求解单源节点最短路径问题。并为讨论新的互连网络拓扑结构的直径和故障直径问题以及单源广播算法提供了一条新的思路。

广度优先搜索算法在螺旋立方体中的应用

本文给出互连网络上的广度优先搜索算法,并将其应用到螺旋立方体上。给出了n维螺旋立方体TQn的直径的另外一种证明方法;该算法可能用来求解单源节点最短路径问题。为讨论新的互连网络拓扑结构的直径和故障直径问题提供一条新的思路。

树的广度优先搜索算法在VFP中的实现

介绍采用数据表作为存储结构,使用树型控件显示树的结点和层次关系。通过建立表、访问表来实现树的存储和广度优先搜索。

基于BFS的多核并行连通区域检测算法

针对一般的连通区域检测算法速度较慢、需多次扫描等问题,本文结合队列的先进先出思想,提出基于广度优先搜索(BFS)的连通区域检测算法。该算法是一种非递归的算法,只需要一次扫描即可记录各个连通区域的点,能有效地降低存储空间和运行时间。本文提出基于特定扫描模板处理像素点,避免重复扫描,利用多核并行处理加速算法,实现了真正的并行运算。利用连通区域自左上至右下有序排列的特性,提出一种逆向合并法,简化了区域合并的复杂度。实验结果表明检测速度有了很大提高。

基于图搜索的FTP文件遍历方法研究

分析了FTP协议和图的遍历算法,对比了遍历算法的适用性,叙述了采用广度优先算法进行FTP文件遍历的方法,并基于此建立了FTP文件搜索引擎,给出了应用实例。

基于模糊规则和BFS算法的行人疏散模型研究

为建立更加真实的行人疏散模型,基于模糊规则和广度优先搜索(BFS)算法,利用元胞自动机,提出1种优化的行人疏散模型。引入动态模糊速度规则,建立移动速度与周边环境的模糊对应关系,从而模拟行人在不同环境下的运动速度;通过设定危险度规则,使用基于双端队列的BFS算法快速计算每个格子距离安全出口的“静态危险度”,并与出口处人群密度的“动态危险度”耦合,使元胞自发地向“总危险度”更低的方向移动;结合动态速度规则建立1种基于排队理论的出口疏散机制。结果表明:所建模型能够再现行人流自组织现象,真实地反应行人不同的移动方式以及疏散的具体过程;模型考虑了出口排队疏散机制对疏散时间的影响,使疏散效率得到提高,为行人疏散模型的建立以及公共场所的设施布局等应急疏散预案提供有效参考。

供水管网水龄的逐节点遍历简化算法

基于水龄的定义,设计逐节点遍历简化算法计算供水管网节点水龄。此法克服了国内传统通过寻找不同的水源到节点的路径而进行广度优先搜索的算法,以及国外常用的划分管段为若干片段并将水龄作为水质的特例来逐时段模拟的拉格朗日传输算法的不足,建模简单,运算快速,结果准确,从而为管网水质的进一步计算和模拟提供了基础理论模型与算法参考。

FTP文件遍历方法研究与应用

分析了FTP协议和图的遍历算法,对比了遍历算法的适用性,叙述了采用广度优先算法进行FTP文件遍历的方法,并基于此建立了FTP文件搜索引擎,给出了应用实例。

基于图遍历的计算DEM数据洪水淹没范围的算法

针对数字高程模型(digital elevation model,DEM)大区域数据量大,而常用的洪水淹没算法(如种子蔓延法)不适用于对DEM的分块计算和分次存储,且用时和耗内存大,设计了一种使用图遍历来有效计算洪水淹没范围的算法,对DEM数据分条带读入计算机内存,然后采用块码压缩方式将潜在淹没区域压缩成块存入磁盘,使用广度优先搜索的图遍历方法读取数据。该算法设计逻辑清晰、实用性强且运算效率高,适用于大范围地形复杂的淹没区域。选取北京市、四川省的DEM数据进行实验,实验结果验证了该算法满足计算快速、占用内存少的要求。

一种消除类游戏的自动完成系统的设计与实现

在游戏领域,消除类游戏一直受到大家的欢迎,其代表游戏是连连看和消消乐。消消乐游戏的玩法是在一定范围内,寻找多个相同属性(同颜色、同形状等)的游戏块组。被点击的游戏块组将消失,玩家获得分数,以无法继续消除或者超时作为游戏结束条件。提出了一种消消乐游戏的自动完成系统。该系统根据游戏给出的初始状态图,使用广度优先遍历(BFS)算法和蒙特卡洛树搜索(MCTS)算法,基于特定的策略给出当前的走法,并根据游戏的规则,预测当前走法的后续状态图,如此循环,从而实现游戏自动完成。

基于差值的动态屏幕截取快速算法

分析了现有的屏幕截取方法在多媒体网络教学中所存在的不足,提出了一种基于差值的动态屏幕截取快速算法,并给出了该算法的具体实现。该算法通过对屏幕信息变化的区域进行分析,将屏幕划分为小块矩形区域,动态提取并进行判断,采用广度优先搜索算法、权重策略、循环遍历机制与随机点策略,能够快速、有效地获取前后两屏信息的差值部分。实验证明,当前后两屏幕间信息变化在一定范围之内时,该算法明显地提高了截屏速度,减少了对屏幕冗余信息的读取,提高了教学过程中屏幕信息交互的流畅性。

关于AOE网中关键路径求解算法的研究

介绍AOE网中关键路径的相关概念,通过算法描述和实例,探讨基于拓扑排序求解、P矩阵的求解和广度优先搜索遍历(BFS)方法三种算法,求解AOE网中关键路径的实现过程,并进一步从算法的时间复杂度、数据结构形式及实现的容易程度等几方面分析三种求关键路径算法的优劣。

一种基于位置信息的MANET网络多路径路由方法

本文提出的方法在目的端利用获得的中间节点位置信息来生成无向图,再利用广度优先遍历算法BFS计算出另外一条不相交路径。使用每包分配方案把业务分配到两个完全不相交路径中,模拟结果表明该路由方法能够实现较高的投递率、较低的控制开销和较低的端到端延迟。

互连网络故障直径的研究

考虑了至多可以删除多少个顶点才能保证互连网络的连通,给出了网络的容错能力。根据Menger定理可以得到BC互连网络之间至少存在n条内部节点互不相交的路径。利用广度优先搜索的思想,给出了求任意两个节点之间的n条内部节点互不相交,且在两点间所有路径中是最短的n条路径的算法。该算法为网络故障直径的研究提供了依据。而且,在故障存在但是网络连通的情况下,可以求得网络中任意两节点间的n条最并行路径,提高了网络的容错能力。本文对提出的方法及算法的正确性进行了证明,为研究互连网络的性质提供了新的研究方法。

多无人机对组网雷达的协同干扰控制策略研究

本文考虑多架电子战飞机(EWA)对组网雷达系统的协同干扰问题,采用最优化方法建立多EWA协同干扰组网雷达的最优控制模型。求解每架EWA的运动参数,建立多EWA协同干扰控制策略,在组网雷达系统中形成一条或者多条虚拟目标航迹。算法以实现多EWA快速高效工作为目的,即利用最少数量的EWA和最少的协同操作步骤完成对组网雷达的欺骗,在EWA的飞行条件约束以及组网雷达信息下,利用广度优先搜索(BFS)算法和禁忌搜索(TS)算法进行求解。仿真实验分析了所建立模型的合理性,实验结果验证了所提出多EWA协同干扰组网雷达控制策略的可行性和有效性。

数据结构期末复习提要

1 绪论 1.1 重点掌握的内容 (1)数据结构的二元组表示,对应的图形表示,序偶和边之间的对应关系.

基于峰值网格改进的小波聚类算法

针对小波聚类算法在不同网格划分尺度下表现出的聚类效果差异,提出了一种基于峰值网格的改进方法。算法主要针对小波聚类中连通区域的检测方式进行改进:首先,将小波变换后的空间网格依网格值的大小进行排序;然后利用广度优先搜索的方式遍历每一个空间网格,以检测经小波变换后数据中的峰值连通区域;最后,标记连通区域并将其映射到原数据空间中,以得出聚类结果。在8个人工数据集(4个凸数据集与4个非凸数据集)和UCI数据库中的2个真实数据集上的实验结果表明,改进算法在低网格划分尺度下有着良好的表现,与原小波聚类算法相比,这个算法对网格划分尺度的需求降低了25%~60%,并且在相同的聚类效果下减少了14%的聚类所需时间。

基于无线通信的智能火灾疏散系统设计

针对现有的火灾系统无法在陌生复杂情况下实现快速安全疏散的功能,提出了基于广度优先算法的智能火灾疏散系统。该智能火灾疏散系统采用了三级架构,传输基于无线通信技术,利用改进的广度优先搜索算法,实现了楼宇复杂通道智能疏散的功能。针对陌生场所紧急疏散逃生效率低、路线不清晰等问题,采用灯流进行疏散引导,实现智能灯流输出。灯流流向即疏散路径方向,达到快速安全疏散的目的。对设计结构进行3D打印封装、现场测试。测试结果表明,在待机状态下,系统自动进行节点巡检;发生火情时,系统自动计算最佳安全逃生路线,智能规避起火点,并输出相应灯流引导疏散;当地震等非火警紧急情况发生时,可实现一键疏散。