`
lovecontry
  • 浏览: 1029819 次
文章分类
社区版块
存档分类
最新评论

求图的简单路径和回路

 
阅读更多

下面是用邻接表存储无向图,然后输出图中指定顶点间的指定长度的简单路径,简单路径就是路径中的顶点不重复,还有一个就是求出图中经过某顶点的回路,都是对图的遍历算法的应用,主要是深度优先的遍历,加上简单的回溯。

下面是代码:

主函数文件


测试结果:

下面是生成的无向图示例:

为了更好得理解回溯的过程,可以画画像下面这样的示意图,比如我求 V1 到 V3的长度为3的路径的过程


图可能和你画的不一样,但是主要就是理清一下思路,不会在一重重的递归中乱掉

分享到:
评论

相关推荐

    用贪心算法求解哈密顿回路

    该程序用C语言编写(在VC++环境下运行即可),使用贪心算法求得最短哈密顿回路的近似解,简单易懂。 该程序用C语言编写(在VC++环境下运行即可),使用贪心算法求得最短哈密顿回路的近似解,简单易懂。

    基于MATLAB计算关联矩阵 回路矩阵 割集矩阵 路径矩阵

    电网络的课堂作业,希望对以后的人有所帮助,不过这个过程还是比较简单的,希望后人改进。

    flip-geodesics-demo:使用快速简单的边缘翻转算法在表面上构造测地路径,回路和网络。 C ++演示应用程序及更多

    该算法将沿三角形网格边缘的路径(或路径的回路/网络)作为输入,并将输出拉直为测地线(即,一条直线或等效地沿曲面的局部最短路径)作为输入。 该程序以毫秒为单位运行,非常健壮,并有力保证不会在路径中创建新...

    三边交换简单算法,哈密顿回路

    提供一种求解最优哈密尔顿的算法---三边交换调整法,要求在运行jiaohuan3(三交换法)之前,给定邻接矩阵C和节点个数N,结果路径存放于R中。 bianquan.m文件给出了一个参数实例,可在命令窗口中输入bianquan,得到...

    ACM培训资料数据结构与算法.pptx

    6 例 1 5 7 3 2 4 G2 6 例 2 4 5 1 3 6 G1 路径:1,2,3,5,6,3 路径长度:5 简单路径:1,2,3,5 回路:1,2,3,5,6,3,1 简单回路:3,5,6,3 路径:1,2,5,7,6,5,2,3 路径长度:7 简单路径:1,2...

    图——基本概念和类型定义

    图是一种非线性结构。 ...这个图是由V1,V2,V3,V4,V5五个顶点和七条边组成的。 相关术语: 有向图:每条边都没有方向的图 无向图:每条边都是有方向的图 如: 完全图:任意两个点都有一条边相连 如

    数据结构实验报告(C++) 实验3;图结构实验指导 程序源码

    整理一下之前的作业,说不定会帮上别人 如果其中选做题没有源码或没有运行截图,那是因为作者也未完成,请见谅 题目1.统计有向图各顶点的度 ...题目6.(选做题)判断两个顶点间是否存在指定长度的简单路径

    Matlab十大算法

    说明: 十大算法MATLAB程序,可用于数学建模,算法和程序相对应 十大算法 十大算法\dijkstra 十大算法\dijkstra\dijk.txt 十大算法\Floyd算法 十大算法\Floyd算法\floyd.txt 十大算法\Floyd算法\中国数学建模-...

    OpenSAL1.1

    图论算法(兼容有向图,无向图)包括:广度和深度优先遍历、确定图是否存在回路、拓扑排序、强连通分支、欧拉环(欧拉路径)、最小生成树(Kruskal、Prim)、单源最短路径(3种)、每对顶点间最短路径(2种)、最大...

    数据结构习题答案(全部算法)严蔚敏版

    7.7.2 有向无环图的拓扑排序和求关键路径 习题七 第8章 查找 8.1 基本概念 8.2 静态表查找 8.2.1 顺序表的查找 8.2.2 有序表的查找 8.2.3 索引顺序表的查找 8.3 动态查找表 8.3.1 二叉排序树和二叉平衡树 ...

    relay-aex.rar_chemicalo7a_relay

    数据结构里的判断两点之间是否有简单路径和判断是否有简单回路,

    电路分析基础:基尔霍夫定律KCL.ppt

    项目二 简易万用表的制作 任务 1. 基尔霍夫定律 2. 电阻的串联、并联与混联 3. 电压源和电流源的等效变换 4. 支路电流法 5. 叠加定理 6. 戴维南定理 7. 最大功率传输定理 2.1 基尔霍夫定律 基尔霍夫定律包括基尔霍夫...

    电路分析基础:基尔霍夫定律KVL.ppt

    基尔霍夫电压定律 (KVL) 在集总参数电路中,任一时刻,沿任一闭合路径绕 行,各支路电压的代数和等于零。 I1 + US1 R1 I4 _ + US4 R4 I3 R3 R2 I2 _ U3 U1 U2 U4 (1)标定各元件电压参考方向 U2+U3+U4+US4=U1+US1 ...

    数据结构与算法分析C描述第三版

     8.6 按秩求并和路径压缩的最坏情形   8.7 一个应用   小结   练习   参考文献  第9章 图论算法   9.1 若干定义   9.2 拓扑排序   9.3 最短路径算法   9.3.1 无权最短路径   9.3.2 ...

    算法导论(part1)

    ·第34.5节给出了对NP完全问题的一个有所扩展的综述,并新增了对哈密顿回路(hamiltonian-cycle)与子集和(subset-sum)问题的NP完全性的证明。 对书中的每一节,几乎都做了重新编辑,修正了说明和证明中的错误,使之...

    历届系统分析师考试数学知识点细分统计

    2005下 24~25 Pert图 关键路径 最早开始时间 2005下 54 最短路径有几条 2005下 55 真命题判断 2005下 56 命题形式化 2005下 57 集合的性质 2005下 58 集合等价关系 2005下 59 强联通图 2005下 60 偏序关系 经济...

    利用栈写的简单的迷宫代码

    自己写的简单迷宫代码 利用栈 找到一个从入口到出口的路径 解决了回路问题 能动态显示寻径过程。开发环境 vc6.0

    数据结构与算法分析

     8.6 按秩求并和路径压缩的最坏情形   8.7 一个应用   小结   练习   参考文献  第9章 图论算法   9.1 若干定义   9.2 拓扑排序   9.3 最短路径算法   9.3.1 无权最短路径   ...

    PCB技术中的高速电路PCB的地弹

    考虑一种简单的情况,信号路径的参考平面为器件UI、U2的“地”,而且元件的信号引脚和地引脚距离不紧邻。  图 地弹产生机理  根据基本电磁定律,当回路中有电流通过时,信号路径和返回路径周围都会产生磁力线圈...

Global site tag (gtag.js) - Google Analytics