首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2
admin
2019-08-01
75
问题
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。
(1)给出完成上述功能的图的邻接表定义。
(2)定义在算法中使用的全局辅助数组。
(3)写出在遍历图的同时进行拓扑排序的算法。
选项
答案
(1)邻接表定义 typedef struct ArcNode{ int adjvex; struet ArcNode * next; }ArcNode; typedef struct VNode{ vertype data: ArcNode*firstare: }VNode,AdjList[MAX]; (2)全局数组定义 int visited[]=0;finished[]=0;flag=1; //flag测试拓扑排序是否成功 ArcNode木final=null: //final是指向顶点链表的指针,初始化为0 (3)算法 void dfs(AdjList g,vertype v){ //以顶点v开始深度优先遍历有向图g,顶点信息就是顶点编号 ArcNode*t: //指向边结点的临时变量 printf(”%d”,v): visited[v]=1; P=g[v].firstarc; while(p!=null){ j=p一>adjvex; if(visited[j]==1&&finished[j]==0)flag=0: //dfs结束前出现回边 else if(visited[j]==0){dfs(g,j);finished[j]=1;} p=p一>next: }//while t=(ArrNode*)malloc(sizeof(ArcNode)); Iit请边结点 t一>adjvex=v:t->next=final;final=t; //将该顶点插入链表 }//dfs结束 int dfs_Topsort(Adjlist g){ //对以邻接表为存储结构的有向图进行拓扑排序,拓扑成功返回1,否则返回0 i=1: while(flag&&i<=n) if(visited.[i]==0){dfs(g,i);finished[i]=1;}//if return(flag); }
解析
转载请注明原文地址:https://kaotiyun.com/show/TkCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列哪一个不是罗马王政时代的管理机构?()
明朝初加强专制统治的措施中,与后来宦官专权有直接关系的是()。
太平天国在1853年冬颁布的纲领性文件是()。
建国以来,根据我国民族状况自身特点,民族自治地方人民代表大会依据全国人民代表大会制定的有关法律,先后制定了若干自治条例和单行条例;全国依法建立了155个民族自治地方,少数民族当家作主的权利得到充分保障。同时,国家采取一系列措施,加大支持力度,促进了民族自治
戊戌政变发生的时间是()。
西汉的主要赋税形式中,征收对象是儿童的是()。
两极格局结束后,世界形势发展的总态势的基本特点()
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
支持多道程序的操作系统,区别于其他操作系统的主要特征为()。
以下关于图的说法正确的是()。.I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在Ⅲ在.AOE网中一定只有一条
随机试题
什么是荧光探伤?
在CFC中,()对大气层中的臭氧层起破坏作用。
请问“实行保税”和“全额征收关税”含义和实行办法是什么?
甲公司为一家制造企业。2×17年4月1日,为降低采购成本,自乙公司一次购进了三套不同型号且有不同生产能力的设备X、Y和Z。甲公司以银行存款支付货款880000元、包装费20000元。X设备在安装过程中领用生产用原材料账面成本20000元(未计提存货跌价准备
【2015年广西.单选】有利于教育逐级普及的学制是()。
行政法规范在对行政关系加以调整后所形成的一种行政法上的权利义务关系即行政法律关系,下列不属于行政法律关系特征的一项是()。
5kg肥皂溶于300L水中后,以每分钟10L的速度向内注入清水,同时向外抽出混合均匀的肥皂水,问何时余下的肥皂水中只有1kg肥皂.
Writeanessayof160-200wordsbasedonthefollowingdrawing.Inyouressay,youshould1)describethedrawingbriefly,
Youwillhearfivedifferentbusinesspeopletalkingaboutpartnerships,oneformofbusiness.Foreachextracttherearetwota
Enoughsleepisimportanttohealth.Theamountofsleep【C1】_______dependsontheageofthepersonandtheconditionsinwhich
最新回复
(
0
)