首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
admin
2019-08-01
60
问题
对于一个使用邻接表存储的有向图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://www.kaotiyun.com/show/QVCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
公元9~13世纪是西欧封建庄园的兴盛时期,典型的庄园采用()的剥削方式。
关于垄断组织的积极作用,不正确的说法是()。
太平天国作为几千年来农民运动的高峰,所遇到的历次农民运动中不曾有过的新情况是(
法国大革命中,颁布全面限价法案的政治派别是
《共产党宣言》指出:“资产阶级在历史上曾经起过非常革命的作用。”其中包括①“使生产工具,从而使生产关系,从而使社会关系不断地革命化”;②“开拓了世界市场,使一切国家的生产和消费都成为世界性的了”;③“使乡村从属于城市”;④“使未开化的和半开化的国家从属于文
商代青铜器的制作技术很高,尤其是礼器的制作,造型美观,纹饰精巧,是水平极高的工艺品,其中主流的花纹是()。
全国高校院系调整的时间是()。
1962,中共中央调整计划目标,工业生产值原定950亿元调为880亿元,钢产量755万吨调为600万吨,并按“经济合理,保留骨干的原则,对企业关停并转。这举措目标
骑士团是罗马教皇推行反宗教改革的工具,其中在波罗的海南岸发挥重要作用的骑士团是()。
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
随机试题
等速运动规律的从动件位移曲线是一条_______,等加速等减速运动规律的从动件位移曲线是一条_______。
随着管理工作的发展,用户希望对系统增加新的功能,或对现有功能提出改进意见由此进行的软件维护叫做()
民法调整的财产关系发生于()。A.纳税人和国家之间B.公司与企业主管机关之间C.行使国家职权的民政部门和政法部门之间D.公民和法人之间
A.柴胡疏肝散B.越鞠丸C.沉香散D.大七气汤E.四磨饮子治疗癃闭肝郁气滞证,应首选
下列与增溶剂的增溶效果无关的是
[2005年第29题]将1个灯由桌面竖直向上移动,在移动过程中,不发生变化的量是:
我国第一部较系统地总结儒家音乐思想的论著是()。
从所给的四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性。
为了使标签控件在显示其内容时不覆盖其背景内容,需进行设置的属性为( )。
使用菜单编辑器设计菜单时,必须输入的项是()。
最新回复
(
0
)