首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
admin
2019-08-01
85
问题
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。
(1)给出完成上述功能的图的邻接表定义。
(2)定义在算法中使用的全局辅助数组。
(3)写出在遍历图的同时进行拓扑排序的算法。
选项
答案
(1)邻接表定义 typedef struct ArcNode{ int adjvex; struct ArcNode *next; }ArcNode; typedef struct VNode{ vertype data; ArcNode *firstarc; }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; //dis结束前出现回边 else if(visited[j]==0){dfs(g,j);finished[j]=1;} p=p一>next: }//while t=(AreNode*)malloc(sizeof(AreNode)); //申请边结点 t->adjvex=v;t->next=final;final=t; //将该顶点插入链表 }//dfs结束 im 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/skCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
以孙中山为首的革命派和以康有为代表的维新派,是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()
试述马丁.路德宗教改革思想的主要内容。
1936年,张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成
1962年2月,中共中央发出《关于改变农村人民公社基本核算单位问题的指示》,规定人民公社的基本核算单位是()。
毛泽东参与重庆谈判的主要目的是()。
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题:哪位皇帝的即位首次应用了秘密立储制?()
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题西周建立之后,派遣同姓贵族和异姓贵族及归顺的异族首领到各地区,建立国家以藩屏护卫周室,分别分在卫、鲁、唐、燕的贵族是()
下列选择中,()不是操作系统关心的主要问题。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页(Page)数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame)。在时刻260前的该进程访问情况见表B一2(访问位即使
随机试题
Haveyoueverseenguidedogs?Guidedogsarethebest"helpinghands"forthe【B1】______Mostguidedogsareboththeireyesand
关于高频电疗法非热效应的概念,错误的是
某肝硬化病人参加晚宴后突然大量呕血,抢救无效死亡。其原因可能是
A.劳力性呼吸困难B.阵发性夜间呼吸困难C.带哮鸣音的吸气性呼吸困难D.带有哮鸣音的呼气性呼吸困难E.端坐呼吸
招标方通过制定标底,使开发商预先明确自己在拟建工程中应承担的财务义务,从而安排资金计划。()
下列四项中合法的电子邮件地址是( )。
________是学校物质文化、制度文化、精神文化的统一体,是经过长期实践形成的。
学生问:“老师,我考试总是很紧张,怎么办?”老师说:“你学习不够努力,没有复习好,所以就紧张了。”从对话中可看出这位老师缺乏()。
A、1B、2C、3D、0A
在三角形ADC中,B、E分别是AC、4D上的点,且BC=2AB,DE=3AE,三角形ADC的面积为36平方米,则三角形AEB面积为()平方米。
最新回复
(
0
)