首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
admin
2018-08-12
63
问题
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
选项
答案
用邻接矩阵存储时,可用以下方法实现: 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
学硕统考专业
相关试题推荐
在晚清地方势力崛起的过程中,属于淮系的有()
下列有关《布列斯特和约》的说法中,错误的一项是()。
詹天佑自主设计修建了中国第一条铁路是在()。
十字军东征
现存迈锡尼线形文字B的材料绝大多数叙述的是迈锡尼的()
编写判定给定的二叉树是否是二叉排序树的函数。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
某浮点机字长16位,其浮点数格式为:阶码5位(含1位阶符),采用补码表示,尾数11位(含1位数符),采用补码表示,且尾数为规格化形式。已知X=0.1011000011×20.0101,Y=0.0001100000×20.1000,试求X+Y.要求写出详细的
下列关于图的叙述中,正确的是____。I.回路是简单路径Ⅱ.存储稀疏图,用邻接矩阵比邻接表更省空间Ⅲ.若有向图中存在拓扑序列,则该图不存在回路
随机试题
在Z37钻床中零压继电器的功能是什么?
最有可能的诊断:如尿妊娠试验(-),该患者可能出现如下子宫内膜病理表现,但除外:
痫病大发作时应
疟疾预防措施除外
某中国企业与某日本企业设立了一家大型中外合资经营企业,关于合营企业的组织机构和经营管理人员的说法正确的是:()
某市政基础设施工程项目业主邀请了三家施工单位参加投标竞争;各投标单位的报价如表1所列,施工进度计划安排如表2所列。若以工程开工日期为折现点,贷款月利率为1%,并假设各分部下程每月完成的工作量相等,并且能按月及时收到工程款。问题就甲、乙两
被审计单位的下列事项中,违反分类目标的是()。
赫尔巴特提出的四段教学法的四个阶段是领会、联想、系统、方法。()
马克思指出:“辩证法在对现存事物的肯定理解中同时包含对现存事物的否定的理解,即对现存事物的必然灭亡的理解;辩证法对每一种既成的形式都是从不断的运动中,因而也是从它的暂时性方面去理解;辩证法不崇拜任何东西,按其本质来说,它是批判的和革命的。”这段表述所指明的
GriffithworkedforafirmthatspecializedineconomicdevelopmentinWashingtonD.C.becausesheneededmoneytopayforherd
最新回复
(
0
)