回溯法关于图
发布日期:2021-06-29 15:42:33
浏览次数:2
分类:技术文章
本文共 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月10日 08时24分41秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
力扣的买卖股票的最佳时机 III之解法(Python3)
2019-04-29
LeetCode 合并两个有序链表 解法 (Python)
2019-04-29
力扣的删除排序链表中的重复元素解法 (Python3)
2019-04-29
力扣的环形链表解法 (Python)
2019-04-29
CSS3 帧动画(Sprite,直译叫雪碧图)
2019-04-29
Java 父线程与子线程相互通信的方法
2019-04-29
Redis 六种淘汰策略和三种删除策略
2019-04-29
Java LinkedHashMap
2019-04-29
JPA 多线程同时对一条数据进行Update的问题
2019-04-29
JPA 多线程对数据进行更新,Update和Insert同时存在的问题
2019-04-29
Java 高性能队列Disruptor
2019-04-29
SpringBoot 使用https
2019-04-29
Java 读写锁
2019-04-29
JVM Minor GC、Full GC和Major GC
2019-04-29
SpringBoot @Scheduled 执行两次的问题
2019-04-29
idea maven工程打jar包,运行出现xxx.jar中没有主清单属性的问题解决方法
2019-04-29
java 使用GDAL生产tif格式
2019-04-29
Node,js 事件循环原理(Event loop)
2019-04-29
CSS3&JavaScript 图片分隔切换
2019-04-29
CSS3&JavaScript 瀑布流
2019-04-29