首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2
admin
2019-08-01
79
问题
对于一个使用邻接表存储的有向图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
学硕统考专业
相关试题推荐
中国古代的经济、文化中心本来在北方,后来移到了南方。请结合史实对这一转移过程进行述评。
试述马丁.路德宗教改革思想的主要内容。
罗马法的集大成《查士丁尼民法大全》产生的时间是在()。
重庆谈判中蒋介石始终不承认人民军队和解放区的合法地位,其根本目的是()。
在华盛顿会议上,美英支持中国要求的意图是()
到1869年为止,人类已发现了多少种化学元素()。
康熙五十九年(1720)指定()组织“公行”(“十三行”)专营对外贸易。凡外商税项的征收、货物的交易,以及外商生活的管理等,均归“行商”负责。
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
已知加权有向图G如下,回答下列问题:(1)画出该有向图G的邻接矩阵;(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
随机试题
全球性组织结构的基本组织形式为()
下列哪项是嗜铬细胞瘤最具特征性的临床表现
女性,66岁,因肺炎住院,既往有慢性肺源性心脏病病史,输液过程中突然出现呼吸困难、气促、咳嗽、咳出粉红色泡沫样痰。下列急救措施正确的是
锐器盒盛装以满()为宜。
FIDIC系列合同条件中,()主要用于发包人设计的或咨询工程师设计的房屋建筑工程和土木工程。
江苏现存下列遗迹中,与辛亥革命有关的有()。
执行完下列语句段后,i值为()。intf(f(1));{return((x>0)?x*f(x-1):2);}intI;I=f(f(1));
任何一种教育体制下,都存在着学生资质差异的问题。理想的教育体制,应该面向不同资质的学生,都提供相应的机会。但是,面对高考升学,面对社会对人才的遴选机制,我们常常是无奈地叹息。因此,天才对教育惟一可说的话,是古希腊哲学家第欧根尼的那句名言:“不要挡住我的阳光
外国侵略者通过不平等条约取得的特权中,按时间先后顺序排列应是()。①外国商船和军舰可以在长江各口岸自由航行②外国人可以在通商口岸开设工厂③可在通商口岸建立教堂④领事裁判权和片面最惠国待遇
Britain’seastmidlandswereoncethepictureofEnglishcountryside,aliveWithflocks,shepherds,skylarksandbuttercups--the
最新回复
(
0
)