图的遍历的分析与算法设计

本文分析了图的深度优先搜索和广度优先搜索遍历的思想,用邻接表设计了其算法,并介绍了图的遍历的应用.     

寻找λ-边连通子图的一次遍历搜索算法

寻找图的λ-边连通子图时,可利用深度优先搜索算法,但需要经过λ次的遍历搜索过程才能完成.基于图的邻接矩阵储存结构特点,提出了一种新的搜索算法,可以通过一次遍历搜索过程得到图的λ-边连通子图.对比深度优先搜索算法,新算法结构简单,容易实现,大大提高了算法的执行效率.这种搜索算法也可以用于判定图的连通性.     

深度优先搜索的非递归算法

深度优先法是图的遍历的一种重要的方法。改方法应用广泛,例如电网拓扑结构、DNA网络等复杂图形分析。在大型网络的分析过程中,深度优先搜索的递归算法效率地下。故本文论证了递归算法的优缺点,并用非递归算法实现了深度优先搜索。     

用遍历方式求解图中是否存在回路问题

本文介绍用图的深度优先搜索遍历求图中是否存在回路问题的算法。     

一种因果图模块的划分方法

把因果图转化为贝叶斯网络结构,用深度优先最左遍历方法寻找因果图的故障模块,改进了因果图在安全系统诊断中的应用.     

基于启发式有向圈查询的可疑交易识别研究

可疑交易监测分析是反洗钱研究的一个重要分支.图中存在一种非常重要的结构—有向圈.金融交易数据可以用有向图表示,称为金融交易图,金融交易图中的有向圈是一种可疑交易结构.提出了一种启发式有向圈查询算法,其基本思想是首先求得图中的强连通分量,然后针对每个强连通分量,进行启发式的深度优先搜索,与一般的深度优先搜索不同,该算法利用两个启发式信息来控制深度优先搜索的方向以及要访问的节点.还对节点数至少为3的强连通分量中一定存在有向圈做出了证明.并且对该算法的时间复杂度作了相关分析.该算法降低了论域的规模,从另一个侧面提高了算法性能.实验证明了算法的有效性,及使用启发式信息的必要性.该算法可检测出金融交易图中的有向圈这一可疑交易结构,为反洗钱研究提供技术支持.     

图的深度优先搜索遍历算法分析及其应用

本文通过具体的示例,详细分析以邻接表为存储结构进行图的深度优先搜索遍历的算法和在vc＋＋环境中实现的完整程序,最后介绍了基于该算法一些应用.     

基于带回溯传播信息和编码技术的求解传递闭包方法

求解传递闭包问题是计算机科学中的一经典问题.文章提出了一种新的传递闭包算法,并导出了若干理论结果,能够将任一关系图化为左偏序图,它是基于带回溯传播信息和编码技术的深度优先搜索算法,该算法效率高,且易于实现.     

求有向图的1—因子和1—因子连接

由于利用Ｃｏａｔｅｓ图分析线性电路求取数值解和符号解时其实时性取决于产生有向图的１－因子和１－因子连接。基于图的深度优先搜索，本文提出一种寻找１－因子和１－因子连接的高效算法，并编制了应用程序。     

网络可靠度BDD分析中2种边排序策略的性能比较

网络可靠度二元决策图（BDD）分析过程包含边排序、BDD生成和可靠度评估3个步骤,其中BDD生成和可靠度评估的计算复杂度和BDD尺度线性相关,而BDD尺度取决于边排序．因此,边排序问题是研究网络可靠度BDD分析的核心．在实现广度优先和深度优先2种边排序策略的基础上,针对规则网络（N＊N型和M＊N型）,比较了这2种策略的分析性能．实验数据表明：1）规则网络中广度优先边排序策略优于深度优先边排序策略;2）当M〉N时,广度优先边排序策略在M＊N型网络中的性能表现优于与之等价的N＊M型网络．这些结论为设计更优的启发性边排序策略提供了重要依据．     

偶深度重复加深优先搜索

各种搜索算法的复杂性是以时间、空间和解路径的长度来衡量的。我们知道宽度优先搜索要求过多的存贮空间,深度优先搜索可能花费过多的时间但未必能求得最佳解。本文提出的偶深度重复加深优先算法克服了上述宽度优先搜索算法和深度优先搜索算法的缺点,并在文中证明了它对指数级树搜索是三度优化的。     

递归函数的非递归模拟

讨论递归的内部实现原理，就递归函数如何转换为非递归函数，给出一组转换规则。利用该组规则将图的深度优先搜索(DFS)和n阶勒让德多项式的递归算法转换成了等价的非递归算法。     

混合的深度优先及宽度优先球形译码算法

结合深度优先及宽度优先算法,提出了一种混合算法,将搜索树分成两部分:一部分进行深度优先搜索;另一部分进行宽度优先搜索.利用深度优先搜索的结果裁剪宽度优先搜索中那些距离较大的点,以降低搜索复杂度.该算法合理地综合了2种算法的优点,具有较低的计算复杂度及较高的性能.仿真结果表明,该算法的性能与最优算法相比差别非常小,与宽度优先算法相比节省了大量的计算复杂度,在高信噪比的情况下,计算复杂度的节省尤其明显.     

二部图最大匹配的快速动态优化算法

建立了二部图C=（V，U，E）的二级优先匹配规则，在此规则下，用改进的深度优先搜索对匹配算法进行改进，使得算法能够根据连通分量的个数动态优化算法的性能，使动态最大匹配算法的时间复杂度提高到0（max（｜V｜，｜E｜，m｜E｜））．     

最大公共子图的约束符号求解方法

【目的】探索求解两个图最大公共子图的方法。【方法】建立最大公共导出子图的软约束满足问题(Soft CSP)模型,提出代数决策图(ADD)的符号求解算法。首先,分别对两个图中的变量和值域进行编码,完成两个图的ADD表示;其次,基于深度优先分支定界算法的思想,利用符号ADD的相关操作,实现对最大公共导出子图的求解。【结果】算例结果表明,该方法准确可行。【结论】该方法能有效缩减搜索空间,从而提高问题的求解效率。     

基于垂直二进制位图的频繁模式挖掘算法

采用垂直二进制位图映射事务数据库，提出了用二进制位图生成一种新的NBFP-Tree结构，并据此提出了一种新的频繁模式挖掘算法NBFP-mine. 该算法不产生候选集，对NBFP-Tree结构进行深度优先遍历一次，就可从NBFP-Tree结构上直接查找出最大频繁模式. 最后，从理论分析和实践验证了它的高效性.     

深度优先搜索在给水管网计算中的应用

针对给水管网水力计算中应用比较普遍的环流量法所需的关联矩阵和回路矩阵,以在AutoCAD环境中直接获取的关联矩阵。运用图论的深度优先搜索方法从中寻找管网图的一棵生成树,进而得到计算所需管网图的回路矩阵。减少了数据的输入量,提高了计算速度,完成对管网的水力计算,从而实现AutoCAD画图与水力计算的无缝对接。     

基于gSpan算法的未知化合物毒性预测

gSpan算法是一种基于频繁图的挖掘算法。该算法基于无候选人产生的频繁子图,在图中建立字典序标号,将每个图映射为最小DFS code,再采用深度优先搜索策略挖掘频繁连接子图。与前人算法相比,该算法在生成候选子图时,冗余子图的产生量大大减少;在计算候选子图支持度时避免了大量重复扫描数据库,性能卓越。该文的贡献是将gSpan算法应用在挖掘与已知毒性化合物具有相同子结构的化合物研究工作中,进行未知化合物的毒性预测,对相关领域应用发展具有重要意义。     

基于特定领域建模的代码生成器研究

针对从软件模型到程序代码自动生成的问题,研究了特定领域建模生成器,把深度优先算法和广度优先算法运用到系统生成中。提出了MetaEdit+环境下,基于广度优先算法和基于深度优先算法的代码生成器实现方法。实现了代码自动生成,同时提高了生成代码的可读性,最后结合电子万年历的实例进行验证。     

一种故障树模块的划分方法

故障树中模块的划分可以有效地降低故障树分析的计算代价 .基于在图中寻找强连接节点的算法 ,给出一种线性时间复杂度算法来检测故障树中的模块 .该算法通过对故障树进行两次深度优先最左遍历来实现 ,其复杂度与故障树中的节点数、边数之和呈线性关系