首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
admin
2019-08-01
23
问题
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。
写出在遍历图的同时进行拓扑排序的算法。
选项
答案
算法 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=(ArcNode*)malloc(sizeof(ArcNode)); //,请边结点 t一>adjvex=v; t一>next=final;final=t; //将该顶点插入链表 }//dfs结束 intdfx_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/QVCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
德里苏丹国前三位苏丹均为奴隶,同时皆属于()
中国第一个资产阶级革命团体兴中会建立的时间是()。
材料一:1913年,印度在政府注册的工厂有2744家,1922年时増加到4744家,民族资本获得了丰厚的利润,一战时期因而被印度企业家们称为创业的“黄金时代”。在两次世界大战期间,印度的制糖业和水泥业得到较快的发展,水泥和糖不再依靠进口。第二次世界大战时
近现代以来,国际关系中先后出现了维也纳体系、凡尔赛一华盛顿体系和雅尔塔体系。关于这三个体系共同点的表述不正确的是()。
洋务运动时期,首批赴欧海军留学生派出的时间是()。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
某路由器的IP地址是125.45.23.12,它在以太网上的物理地址为2345AB4F67CD,它收到了一个分组,分组中的目的IP地址是125.11.78.10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。
随机试题
针对偏当前享受型客户的理财目标优先级,在基金和保险行销方面可以做的建议()
将燃气的热能和压力能转变为轴上的机械功的叶轮式机械称为()。
某企业5月31日的银行存款日记账账面余额为88000元,银行对账单余额为99000元,经核对有两笔未达账项,其一:5月29日企业委托银行收款6000元,银行已收款入账,企业尚未收到收款通知;其二:5月30日企业开出转账支票一张5000元,持票人尚未到银
下列关于商业银行理财产品投资运作管理的说法中,错误的是()。
入库单位通常等于货物的最大储存单位。
求因果联系的方法不包括()。
黑龙江省友谊农场某小学的教师上课时间打麻将,并指派学生轮流站岗放哨。家长对这种现象很有意见,这所小学长期以来管理十分松散。校长经常去中心学校办事而不来此小学,教师们开始只是利用午休和课后时间在办公室打麻将,后来愈演愈烈,直至发展到停课“操练”。据了解,只要
货币政策是国家调控宏观经济的一项重要政策,以下属于货币政策工具的有()。
DoyouknowwhattheWhiteHouseis?Perhapssomeofyoudo,whileothersdon’t.TheWhiteHouseisahouseinWashington.T
A、Sendherdaughtertoaprivateschool.B、Helpherdaughterfindagoodjob.C、Criticizeherdaughterandforcehertostudy.D
最新回复
(
0
)