首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2
admin
2019-08-01
44
问题
对于一个使用邻接表存储的有向图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
学硕统考专业
相关试题推荐
论述欧洲一体化的进程及影响。
阅读材料并结合背景知识回答问题:材料到17世纪60年代,伟大的科学学会的时代到来了:英国皇家学会、法国科学院先后成立。此前,科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴,开普勒由德意志皇帝资助;或者靠某些科学“爱好者”、赞助者
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:西汉到北魏赋税制度的变化的基本趋势是()
关于垄断组织的积极作用,不正确的说法是()。
提出“天有常道,地有常数”,“制天命而用之”的思想家是()。
红山文化的代表性墓葬形式为()。
1947年,刘邓大军千里跃进大别山,揭开了战略反攻的序幕。 据此回答问题:之所以把中原地区作为反攻的方向,主要是由于该地区()
以下对于清初恢复发展经济的措施论述正确的一项是()。①停止圈地②“更名田”③奖励垦荒④整顿赋役制度⑤废除匠籍
中国共产党在大革命失败后,根据中国革命的新特点,明确了“工农武装割据”的思想,其核心内容不包括()。
随机试题
下列作品中属于以传记形式写的寓言的是【】
DNA复制时,以序列5′-CAGT-3′为模板合成的互补结构是
重度一氧化碳中毒患者在意识障碍恢复后,经过2~60d的“假愈期”又出现意识障碍,临床考虑诊断为
某设备工程的建设期为3年,第一年贷款额为400万元,第二年贷款额800万元,第三年贷款额500万元,贷款年利率为,5%,则建设期贷款利息为()万元。
城市道桥、铁路(包括轻轨)、工业厂房等建设项目,在建成后的使用过程中可能会对周围环境产生噪声污染。建设单位应依法规定防治措施的时间是()。
我国规定低压电器是指交流电压1200V,直流电压()及以下的电器产品。
【2013年青岛市】个人面对问题情境时,不钻牛角尖,能随机应变、触类旁通。这是发散思维的()。
月亮上有许多大大小小的环形山,多数科学家认为环形山的成因是()。
对一个组织来说,各个组成部分往往是________的,而劣质的部分往往决定了整个组织的水平。为了发挥组织的________作用,释放它的潜力,就必须弥补薄弱环节,使组织能够在市场竞争中处于不败之地。填入画横线部分最恰当的一项是:
庄严的举止.庄严
最新回复
(
0
)