首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。 其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。 其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
admin
2019-08-15
66
问题
对于一个使用邻接表存储的有向图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结束 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); } 提示:此题考查的知识点是图的遍历。对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点v出发遍历,在dfS(v)结束之前,出现从顶点u到顶点v的回边,图中必存在环。由于dfs产生的是逆拓扑排序,故设一类型是指向邻接表的边结点的全局指针变量final,在dfs函数退出时,把顶点v插入到final所指的链表中,链表中的结点就是一个正常的拓扑序列。
解析
转载请注明原文地址:https://kaotiyun.com/show/udCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列各项内容和王羲之的书法成就有关的是()。①开始把字体由隶书转化为楷书②书法代表作有《兰亭序》、《黄庭经》等③他博彩众长,世称“书圣”④其子王献之书法造诣也极高,父子合称“二王”
经六朝时期的发展,南方形成了三个农业发达地区即()。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
在4×100米接力赛中,4个运动员之间存在如下关系:运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交棒给运动员3;运动员3也只有接到运动员2传来的接力棒后才能往前跑,他跑完100米
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
下面关于进程的叙述中,正确的是()。
为了在通用操作系统管理下的计算机上运行一个程序,需要经历几个步骤,但是,()不是一定需要。
某网络拓扑如图A-3所示,路由器R1通过接口E1、E2分别连接局域网1、局域网2,通过接口LO连接路由器R2,并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202.118.2.1,R2的L0接口的IP地址是202.118.2.2,L1接
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(e1,e2.…,em);i=l;while(所剩边数>=顶点数){从图中删去ei;若图不再连通,则恢复ei;i=i+l;
下列关于计算机中指令和数据存放位置的叙述,正确的是()。
随机试题
A.黄色B.红色C.黑色D.绿色E.蓝色硫化氢试验阳性结果是
一名患急性喉炎的小儿,安静时可听到喉呜,并有吸气性呼吸困难,听诊可闻管状呼吸音,患儿心率加快,约130次/分,该患儿喉梗阻程度为
患者,男,54岁。症见足膝红肿、筋骨疼痛。中医辨为湿热下注所致的痹病,处以四妙丸,其药物组成为盐黄柏、苍术、薏苡仁、牛膝。下列关于处方中盐黄柏炮制方法、炮制作用的说法,错误的是
A.第一类医疗器械产品B.第二类医疗器械产品C.第三类医疗器械产品D.第四类医疗器械产品E.第五类医疗器械产品
背景资料:某电力建设公司承接2×1000MW电厂建设工程的总承包任务。考虑工期和专业特长的要求,辅助工程采用分包的方式组织建设。在工程建设中发生如下事件:事件一:在发电机转子安装时,施工单位进行了发电机转子安装前单独气密性试验,在试验
关于SWOT分析中机会和威胁的说法正确的有()。
下列有关定金的说法中,正确的是()。
我国著名乐曲《万马奔腾》是以()为主奏乐器的蒙古族作品。
Usingtheinformationinthetext,completeeachsentence14-18withanexpressionfromthelistbelow.Foreachsentence(14
A、It’sme.B、It’sus.C、It’smine.C
最新回复
(
0
)