回溯法关于图
发布日期:2021-06-29 15:42:33
浏览次数:3
分类:技术文章
本文共 1224 字,大约阅读时间需要 4 分钟。
图的结构体定义
typedef struct { int adjvex; EdgeNode *next;}EdgeNode;typedef struct{ int data; EdgeNode *firstEdge;}Vertex;typedef struct { Vertex adjList[maxsize]; int n,e;}AGraph;
1.假设图G采用邻接表存储,设设计一个算法,输出此图G从顶点vi到vj长度为L的所有简单路径
int visited[maxsize];int path[maxsize];void printAllPath(AGraph *g,int vi,int vj,int d,int L){ EdgeNode *p;int i; if(vi==vj&&d==L) { cout<<"one path:"; for(i=0;i<=d;i++) cout<<<" "; } ++d; path[d]=vi; visited[vi]=1; p=g->adjList[vi].firstedge; while(p!=NULL) { if(visited[p->adjvex]==0) printAllPath(g,p->adjvex,vj,d,L); p=p->next; } visited[vi]=0; --d;}
2.藏宝图,设计一个算法,要求从入口到出口,必须经过v1,v6,不得经过v4
int visited[maxsize];int path[maxsize];int d=-1;int cond(int v1,int v4,int v6){ int flag1=0,flag2=0,flag3=1,i; for(i=0;i<=d;i++) { if(path[i]==v1) flag1=1; else if(path[i]==v4) flag3=0; else if(path[i]==v6) flag2=1; } return flag1&&flag2&&flag3;} void printPath(AGraph *g,int vi,int vj,int v1,int v4,int v6){ EdgeNode *p;int i; if(vi===vj&&cond(v1,v4,v6)) { for(i=0;i<=d;i++) cout<<<" "; } ++d;path[d]=vi; visited[vi]=1; p=g->adjList[vi]->firstedge; while(p!=NULL) { if(visited[p->adjvex]==0) printPath(g,p->adjvex,vj,v1,v4,v6); p=p->next; } visited[vi]=0; --d;}
转载地址:https://codingchaozhang.blog.csdn.net/article/details/85252097 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月11日 07时30分44秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
OpenCV 图像采样 插值 几何变换
2019-04-29
图像处理-仿射变换 AffineTransform
2019-04-29
图像二值化----otsu(最大类间方差法、大津算法)
2019-04-29
图像二值化----otsu(最大类间方差法、大津算法)(二)
2019-04-29
OpenCV编程案例:使用轮廓函数检测连通区域
2019-04-29
opencv使用cvFindContours提取联通域
2019-04-29
C++中MessageBox的常见用法
2019-04-29
ordfilt2函数功能说明
2019-04-29
在图像变换中用最小二乘法求解仿射变换参数
2019-04-29
软件包应用分享|基于RT-Thread的百度语音识别(一)
2019-04-29
12月8日 RCEA - RT-Thread能力认证考试考前通知
2019-04-29
论坛热贴 | RT-Thread音频驱动开发(一)
2019-04-29
基于 Keil MDK 移植 RT-Thread Nano
2019-04-29
【报名截至今晚】12月14日深圳嵌入式与音频开发专题会议预告
2019-04-29
移植 RT-Thread Nano 到 RISC-V
2019-04-29
软件包应用分享|基于RT-Thread的百度语音识别(二)
2019-04-29
在 RT-Thread Nano 上添加控制台与 FinSH
2019-04-29
一站式开发工具:RT-Thread Studio 正式发布
2019-04-29
留言有礼|谢谢你悄悄点了小星星,让我们跃居GitHub RTOS Star榜第一
2019-04-29
功能更新!C 函数也能在 MicroPython 中被调用啦
2019-04-29