首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
admin
2019-08-15
22
问题
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
选项
答案
用邻接矩阵存储时,可用以下方法实现: void Print(int v,int start){ //输出从顶点start开始的回路 for(i=1;i<=13;i++) if(g[v][i]!:0&&visited[i]==1){ //若存在边(v,i),且顶点i的状态为l printf("%d",v); if(i==start)printf(”\n”); else Print(i,start); break; }//if }//Print void dfs(int v){ visited[v]=1 ; for(j=l;j<=n;j++) if(g[V][j]!=0) //存在边(v,j) if(visited[J]!=1){if(!visited[j])dfs(j);}//if else{cycle=l;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)结束前出现顶点M到v的回边,则图中必有包含顶点v和u的回路。对应程序中v的状态为1,而u是正访问的顶点,若找出u的下一邻接点的状态为1,就可以输出回路了。
解析
转载请注明原文地址:https://jikaoti.com/ti/CsGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题:西汉到北魏赋税制度的变化的基本趋势是()
国民党政府被彻底打垮的战役是()。
鸦片战争失败后,西方列强强迫清政府签订了中国近代史上第一批不平等条约。鸦片战争是中国历史的转折点,对中国历史产生了深远的影响。中国开始逐步沦为半殖民地半封建社会。据此回答问题:中国与外国签订的第一个同盟条约是()
下列选择中,()不是操作系统关心的主要问题。
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
某机的主要部件如下图所示。(1)请补充各部件间的主要连接线,并注明数据流动方向。(2)拟出指令SUB(R1),一(R2)的执行流程(含取指过程与确定后继指令地址)。该指令的含义是进行减法操作,源操作数地址和目的操作数地址分别在
一台模型机共有7条指令,主频25MHz,各指令的使用频率与CPI如下表所示,该机有8位和16位两种指令字长,采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型,16位字长指令为寄存器~存储器(R—M)二地址变址类型(地址码范围在一12
若对n阶对称矩阵A[1..n,1..n]以行序为主序方式下将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组B[1..n(n+1)/2]中,则在B中确定aij(i
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijkstra算法求出从结点A到所有其他结点的最短路由。
设有一个由正整数组成的无序(后向)单链表,编写能够完成下列功能的算法:(1)找出最小值结点,且打印该数值。(2)若该数值为奇数,则将其与直接后继结点的数值交换。(3)若该数值为偶数,则将其直接后继结点删除。
随机试题
女性,39岁,持续心悸3个月,伴双手颤抖,大便次数增多。查体:T37.2℃,P98次/分,皮肤潮湿,突眼,甲状腺Ⅱ度。听诊S1增强。患者心悸最可能的原因是
国家授权投资机构对国有独资公司行使的职权有( )。
朱某于2003年2月8日下午乘三轮客车的途中,扒窃了同车乘客林某的人民币400元,被林某发现后朱某欲跳车逃跑,但林某死死抓住朱某的衣服,朱某便用力挣脱跳下车,同时把林某拖跌落车。林某跌落后头部撞击地面导致颅脑严重损伤而死亡。则朱某的行为不构成以下F哪些犯罪
业主委员会是业主大会的执行机构,业主委员会应当自选举之日起()日内召开首次业主委员会会议,推选产生业主委员会主任1人,副主任1~2人。
阅读下列材料,回答问题。负重的河流这是每一本地理书上都提到过的著名河流,一条河流在哪里出现,从哪里经过,又归属于哪里,决不是偶然的事。塔里
《宋史》中有“国家根本,仰给东南”的文字记载,据此,说明当时社会()。
关于共有,下列表述错误的是()。
甲建筑工程公司(具备建筑行政部门批准的建筑业施工资质,且为增值税一般纳税人)下辖3个施工队、1个金属结构件工厂、1个招待所(均为非独立核算单位),2012年经营业务如下:(1)承包某建筑工程项目,并与建设方签订建筑工程施工总包合同,总包合同明确工程总造
宪法制定的程序不包括以下哪一步()
Choosethecorrectletter,A,BorC.Whatwasthecountryofregistrationoftheboatwhichwasstuckinthickice?
最新回复
(
0
)