首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
admin
2018-08-12
28
问题
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
选项
答案
用邻接矩阵存储时,可用以下方法实现: void Print(int v,int start){//输出从顶点start开始的回路 for(i=1;i<=n;i++) if(g[v][i]!=0&&visited[i]==1){ //若存在边(v,i),且顶点i的状态为1 printf(“%d”,v); if(i==start)printf(“\n”); else Print(i,start); break; }//if }//Print void dfs(int v){ visited[v]=l; for(j=1;j<=n;j++) if(g[v][j]!=0) //存在边(v,j) if(visited[j]!=1){if(!visited[j])dfs(J);}//if else{cycle=1;Print(j,j);} visited[v]=2; } void find_cycle(){ //判断是否有回路,有则输出邻接矩阵。visited数组为全局变量 for(i=1;i<=n;i++)visited[i]=0; for(i=1;i<=n;i++)if(!visited[i])dfs(i); } 提示:此题考查的知识点是图的遍历。有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问,已访问但其邻接点未访问完,已访问且其邻接点已访问完。下面用0、1、2表示这三种状态。前面已提到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v和u的回路。对应程序中v的状态为1,而u是正访问的顶点,若找出u的下一邻接点的状态为1,就可以输出回路了。
解析
转载请注明原文地址:https://kaotiyun.com/show/nMRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
17世纪英国资产阶级革命中,曾利用了古老文件同专制王权作斗争。这一古老文件是()
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
圣德太子《宪法十七条》规定的是()。
下列对近代社会思潮产生的先后顺序排列正确的是()。①人文主义②自由主义③理性主义④重商主义
下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥
下列关于罗马共和国政治制度的叙述,不正确的是()。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
随机试题
甲、乙同居多年后决定结婚并在民政局进行了登记,则下列说法正确的有()。
患儿女性,7岁。近6个月来双眼睑下垂。近日来发现复视,晨轻晚重。双眼的外展、内收困难。肌电图示肌肉动作电位的幅度很快递减。其重症肌无力类型是患儿女性,7岁。系眼肌型重症肌无力。近2周来发热、呛咳,应用静脉滴注林可霉素(洁霉素)和庆大霉素后,出现呼吸困
肝硬化出现全血细胞减少的主要原因是
生态工业的发展将促进()模式的建立。
下列关于自然经济的表述,正确的有()。
下列对银行体系货币创造功能的描述,不正确的是( )。
Aspeopleinrichcountriesknowverywell,eatingtoomuchfoodandburningtoolewcaloriesiswhyasubstantialnumberofus
下列说法中,正确的是
建立孩子自尊心的最好方法是尊重孩子,把孩子当作和自己完全平等的人来对【166】。当父母尊重孩子的时候,他开始尊重自己,进而他会尊重别人。这样他的“人化”过【167】才能启动。建立孩子自尊心的第二个重要的方法是无条件地爱孩子。当父母无条件地爱孩子的【168】
A、 B、 C、 A
最新回复
(
0
)