首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
admin
2019-08-01
42
问题
对于一个使用邻接表存储的有向图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
学硕统考专业
相关试题推荐
论述欧洲一体化的进程及影响。
苏联“十四大”“十五大”后经济建设的核心内容是()
资产阶级改良道路行不通,资产阶级共和国方案夭折,其共同原因在于()。①中国封建势力的强大②帝国主义列强的直接破坏③资产阶级的软弱妥协④没有充分地发动人民群众
隋唐时的冶铸业已普遍采用的技术包括()①切削②抛光③焊接④使用机械动力
标志着整风运动开始向反“右派”斗争转变的重要文件是()。
下列国家中不是不结盟运动发起者的是()。
1980年1月,邓小平在《目前的形势和任务》提出的中国人民长期奋斗的三件大事是()。
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
就绪队列中有n个进程等待使用一个CPU,那么,如果采用不同的调用算法,就有()种调度顺序。
假定某采用页式虚拟存储管理的计算机系统中,主存储器容量为1GB,被分为262144块物理块,物理块号为0,1,2,……,262143。某进程的地址空间占4页,逻辑页号为0,1,2,3,被分配到主存储器的第20,45,101,58号物理块中。回答:
随机试题
男,40岁,急性化脓性腹膜炎,血压75/45mmHg,经积极抗休克治疗,仍不好转,此时最适宜的治疗是()
A、B两山村之间的路不是上坡就是下坡,相距60千米。邮递员骑车从A村到B村,用了3.5小时;再沿原路返回,用了4.5小时。已知上坡时邮递员车速是12千米/时,则下坡时邮递员的车速是()。
当二级市场ETF交易价格低于其份额净值,即发生折价交易时,大的投资者可以通过在二级市场买进(),然后在一级市场赎回份额,再于二级市场上卖掉()而实现套利交易。
股份有限公司的股东出席股东大会会议,所持每一股份有一表决权。公司可以以持有的本公司股份进行表决。()
教育改革的核心是()。
下列有关财务报表审阅的说法,恰当的有()。
人们必须重视书本知识,这是因为()。
往往,无法改变生存环境的无力感,或相信有某个人在某个地方遥控我们行动的想法,都会使我们对学习产生排斥情绪;相反的,如果知道命运是操纵在自己的手中,我们就会努力不断地学习和应变。因此,当我们对自己的行动有真正的责任感时,学习的速度也会变快。这段话主要支持这样
广告,即确定的组织或个人为了一定的目的,【145】付出的费用,在规定的时间【146】,按照要求,由指定的媒体,将真实信息传播出去的一种【147】活动。这个定义从实践中来,【148】能反映广告的本质属性,也能够解释除商业广告【149】的一些广告现象。如“征婚
Accuraterepresentationandreportingisvitalinthemediabecause______.InLine4,Para.3,theword"exacerbated"ismost
最新回复
(
0
)