首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
admin
2019-08-01
78
问题
对于一个使用邻接表存储的有向图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]==l&&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); }
解析
转载请注明原文地址:https://kaotiyun.com/show/ctCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
马克思第一次明确论述无产阶级历史使命和无产阶级必须与科学理论相结合思想的著作是()。
1217年,英格兰的《森林宪章》允许平民百姓在王室森林中放牧牲畜、挖掘水渠并从事其他农业活动。颁布该宪章的主要目的在于()
论述欧洲一体化的进程及影响。
阅读材料并结合背景知识回答问题:材料到17世纪60年代,伟大的科学学会的时代到来了:英国皇家学会、法国科学院先后成立。此前,科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴,开普勒由德意志皇帝资助;或者靠某些科学“爱好者”、赞助者
以下不属于泰州学派的哲学思想的是()。
列宁在()报告中论证了在俄国实现和平过渡的可能性和必要性。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构
随机试题
关于真理标准问题的讨论及其意义。
医疗器械生产经营企业、使用单位发现或者知悉医疗器械导致严重伤害、可能导致严重伤害或死亡的事件,应当在几个工作日内向所在地的省级医疗器械不良事件监测技术机构报告?()
营养性缺铁性贫血的实验室改变不包括下列哪项
如果要比较两宗房地产价格,则需要将它们先转换成相同的年限下的价格。()
某砌体结构的多层房屋(刚性方案),如下图所示。试问,外墙在二层顶处由风荷载引起的负弯矩标准值(kN·m)应与下列( )项数值最为接近。提示:按每米墙宽计算。
利润表至少应当单独列示反映信息的项目有()。
根据《总会计师条例》的规定,总会计师是()。
意向申报指令应当包括证券账号、证券代码、买卖方向和本方交易单元代码等内容。()
随着我国经济的快速发展,国内能源消费需求量越来越大。由于我国对石油进口的_________较大,所以国际油价上涨、中东政局变化等因素,都会对我国石油能源安全构成_________危险。同时由于石油具有流动性好,便于开采、输送和使用的特点,近年来国内石油消费
Awriter’sattemptstoreproducefolkspeechcanbeanassettothehistorianofpronunciation.
最新回复
(
0
)