共查询到18条相似文献，搜索用时 140 毫秒
1.
这一章首先介绍了图的基本概念和图的各种存储结构;接着讨论了图的深度优先遍历和图的广度优先遍历,求图的最小生成树的普里姆算法和克鲁斯卡尔算法,以及求图的从一顶点到其余各顶点的最短路径和每一对顶点之间的最短路径。最后讨论了图的拓扑排序和关键路径问题。 相似文献
2.
提出了平面散乱数据点集曲线重构的最短路逼近算法,它创造性地把散乱数据点集的曲线重构问题转化为图论中带权连通图的最短路求解问题。新方法根据散乱数据点的分布情况构造平面上的势函数,并对散乱数据点集进行Delaunay三角化。根据势函数对Delaunay三角网格的每条边赋一个权值,生成带权连通图。在带权连通图上生成重构曲线两端点间的逼近路径,简化逼近路径,找出该路径上的关键点。以关键点为控制点,势函数值为权值,生成有理B样条曲线。最短路逼近算法在实验中取得很好的效果,成功解决了移动最小二乘法难以解决的具有尖点特征的数据点集的曲线重构问题。 相似文献
3.
最小生成树问题的Kruscal算法的一种实现方法 总被引：1，自引：0，他引：1
本文讨论了针对带权连通图的一种可行性存储结构———单链表结构的构造问题 ,并研究了在该结构上构造最小生成树的算法 .算法已在机器上得到了实现 相似文献
4.
为了节约软件测试成本,减少测试用例数量,提出了一种利用蚁群算法直接从UML活动图中生成测试用例的方法。通过对UML活动图和蚁群算法进行形式化规约,构造人工蚁群,然后依据DFS遍历由UML活动图转化的有向连通图G,最后生成测试用例。通过仿真模拟,对提出的方法进行验证以及对实验结果进行分析,证明了该算法的可行性和有效性。 相似文献
5.
根据数据结构中求一个带权无向连通图的最小生成树算法的特点,文章给出了Kruskal算法的一个简便而完整的C语言实现。特别是对不连通子图的刻画,只引进了一个一维数组就解决了问题。 相似文献
6.
《实验室研究与探索》2017,(1):117-122
针对现有无线传感器网络数据汇集算法延时较大这一不足,对最小延时数据汇集树和传输调度问题进行了研究。提出一种基于度约束的汇集树构建算法(DCAT)。该算法按照BFS方式遍历图,当遍历到每个节点时,通过确定哪些节点与汇点更近来确定潜在母节点集合。然后,选择图中度数最小的潜在母节点作为当前被遍历节点的母节点。此外,为了在给定的汇集树上进行高效数据汇集,文中还提出两种新的基于贪婪的TDMA传输调度算法:WIRES-G和DCAT-Greedy。利用随机生成的不同规模的传感器网络,参照当前最新算法,对本方法的性能进行了全面评估。结果表明,与当前最优算法相比,本调度算法与汇集树构建算法结合起来,可显著降低数据汇集的延时。 相似文献
7.
8.
以有向赋权图为工具,通过对满足限制条件的最短有向路径问题的讨论,给出了两个组合优化问题——大学教学计划的编排问题和交通网络中路径规划问题的有效算法,并通过实例进行了算法分析． 相似文献
9.
针对多约束QoS路由选择问题,将其转化为一个多约束赋权图最短路径问题,选择费用、带宽、时延和丢失率为QoS参数.针对一种免疫算法的不足,利用基于相似结构的小生境技术和共享算子对免疫算法加以改进.实验表明,该算法有较好的性能,大幅提高了QoS路由选择的效率. 相似文献
10.
11.
赵一平 《乌鲁木齐成人教育学院学报》2006,14(2):86-87
Hamilton问题是图论的一个重要问题,判定一个图是否是Hamilton图虽然已找到了几个充分条件和必要条件,但不是充要条件,而且用这些条件来判定一个图是否是Hamilton图非常不好用,本文给出一个算法,对于任意给定的无向简单连通图可以判定其是否是Hamilton图,如果是Hamilton图,还可给出Hamilton回路。 相似文献
12.
基因组重排问题是分子生物学中的重要问题,进化问题的研究可归结为进化距离问题的研究.即计算从一个基因组进化为另一个基因组所需的最少的进化变换数目.可借助基因组之间的圈图研究翻转进化问题,Hannenhalli给出了一个计算圈图分支的一个线性时间算法,但考察的对象为圈图上的圈集合,且需要一些等价变换.从边集合出发给出了计算有向基因组的圈图连通分支的线性时间算法. 相似文献
13.
刘淋 《襄樊职业技术学院学报》2010,9(6):25-27
本文对几种有向赋权图的最短路长和路径采用Lingo软件对其求解,并分析了用Lingo解法的简便之处和如何处理赋权有向图中的负权问题。对解决此类问题提供了一种新的途径。 相似文献
14.
图论中的最短路径问题在计算机中有着广泛的应用,特别是城市地理信息系统中很多城市道路网相关问题均可纳入最短路径问题的范畴之中。文章首先对几种常见最短路径的算法进行介绍,重点分析了基于城市应急系统中救援路径的A＊算法,并给出了算法实现。 相似文献
15.
为了解决汽车白车身焊接机器人路径规划不合理的问题,将路径规划问题抽象为TSP模型.本文从图论的角度出发,采用Christofides算法,编写相应的MATLAB程序对一个具体的实例进行仿真.该算法可以有效地解决焊接机器人路径规划问题. 相似文献
16.
具有长度约束的简单路径问题具有较高的应用价值。在一般图中,它是一个NP完全问题,除非NP=P,否则没有多项式时间算法。而对于一些特殊的图,如有向无环图,可以找到多项式时间算法。因此对有向无环图中具有长度约束的简单路径问题进行研究。首先根据有向无环图的特点,建立递归方程,然后根据递归方程给出一个在有向无环图中求解具有长度约束的简单路径问题算法,同时给出一个有向无环图中具有长度约束的简单路径构造算法。为证明算法正确性,进行相应实例验证,把求解该问题的时间复杂度由O（N×T×L）改进为O（（N+|E|）L）,空间复杂度改进为O（|E|+N）。 相似文献
17.
遗传算法在网络动态选路中的应用 总被引：1，自引：0，他引：1
陈皓 《株洲师范高等专科学校学报》2004,9(5):36-38
根据安全传输的要求,提出了一种运用遗传算法来实现网络中动态寻路的方法.且结合运用遗传算法求解图的最小生成树的例子,对一个模拟网络拓扑结构的有权无向图进行了编码,为求解过程建立了相应的模型,并对该模型进行了分析. 相似文献
18.
基于Dijkstra最短路径算法的优化研究 总被引：3，自引：0，他引：3
李健 《渭南师范学院学报》2009,24(5):61-64
最短路径问题是图论研究中的一个重要课题.Dijkstra算法是许多工程解决最短路径问题的理论基础,有着广泛的应用.本文在分析传统Dijkstra算法的基础上,提出该算法在实现方法上存在的一些不足之处,并从节约存储空间和提高运算效率方面对其进行了改进,通过分析与比较,这种改进算法的效率优于传统的Dijkstra算法,具有较好的适用性. 相似文献