首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序,写出在遍历图的同时进行拓扑排序的算法。
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序,写出在遍历图的同时进行拓扑排序的算法。
admin
2014-12-25
70
问题
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序,写出在遍历图的同时进行拓扑排序的算法。
选项
答案
int flag[];count=0;success=1; /*success:测试拓扑排序是否成功*/ InitQueue(Q); voidDFSTopSort(ALGraphG) { /*对以邻接表为存储结构的有向图G进行拓扑排序*/ for(v=0jV
nextarc) if(visited[p->adjvex]&&flag[p一>adjvex]==0) /*DFS结束前出现回边*/ success=0; elseif(!visited[P一>adjvex]) {DFS(G,P一>adjvex);flaq[p一>adjvex]=1;} }
解析
对有向图进行深度优先搜索,可以判定图中是否有回路。若从有向图的某个顶点v出发深度优先遍历,在DFS(v)结束前,出现顶点n到顶点v的回边,图中必有环。用数组flag
=1,表示其邻接点已全部被搜索完。由于深度优先搜索得到的序列是逆拓扑排序序列。因此用队列存放所访问的顶点。算法描述如下。
转载请注明原文地址:https://kaotiyun.com/show/qaVx777K
本试题收录于:
数据结构导论题库理工类分类
0
数据结构导论
理工类
相关试题推荐
UDP是一种不可靠的传输层协议,它非常适合于速率要求_________、而对精确度要求相对较低的网络应用,如视频会议、视频点播和网络电话等。
电子邮件从用户代理发送到邮件服务器所采用的协议是【】
实现数字签名的方法分为对称密钥签名和_____两种。
_____是将密文恢复为明文的变换函数。
请根据以下调查结果绘制计划部分的数据流程图:根据定货合同提供的物资领用计划汇总编写成材料领用计划,再结合材料消耗定额本上的数据计算编写成限额发料文件,打印此文件,并交保管员保存。
下列关于信息的说法正确的是()
为保证在规定时间内完成项目的管理是()
下列聚合函数中,不忽略空值的是()
在元组关系演算中,与公式P1P2等价的公式是()
一个有10个顶点的有向图,它最多能有________条边。
随机试题
根据《反恐怖主义法》的规定,甲县公安机关在调查恐怖活动嫌疑时,对恐怖嫌疑人员黄某采取约束措施,下列说法错误的是()。
套利的经济学基础是()。
匹夫见辱,拔剑而起,挺身而斗,此不足为勇也。
设有某Internet用户,其POP主机域名是mail.hz.zj.cn,帐户名为zhangsan,则相应的E-mail地址是_______。
影响CT图像质量的因素包括
在悬臂浇筑混凝土斜拉桥的梁施工检测中,对于斜拉索锚具轴线与孔道轴线偏位的要求是()。
以下关于上市公司分红说法正确的有()。Ⅰ.公司发展阶段属成熟期且无重大资金支出安排的,进行利润分配时,现金分红在本次利润分配中所占比例最低应达到80%Ⅱ.公司发展阶段属成熟期且有重大资金支出安排的,进行利润分配时,现金分红在本次
刑讯逼供罪只能由()构成。
窗体上有一个名称为Command1的命令按钮,单击该按钮时所实现的功能是产生10个随机整数,然后从键盘输入一个整数,查找该数在数组中的位置。若找到,输出该数的位置;若没有找到,给出相应的提示。该命令按钮的单击事件过程如下:PrivateSubCo
下列数据结构中,属于非线性结构的是
最新回复
(
0
)