首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
admin
2019-08-01
89
问题
对于一个使用邻接表存储的有向图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
学硕统考专业
相关试题推荐
简述罗马共和国衰亡的原因。
“二战期间,美国研制了原子弹并用于实践;1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道;德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
太平天国作为几千年来农民运动的高峰,所遇到的历次农民运动中不曾有过的新情况是(
提出“天有常道,地有常数”,“制天命而用之”的思想家是()。
新文化运动前期的指导思想是()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
若某浮点机基数为4,尾数采用补码表示,则该浮点机的规格化尾数形式为()。
某浮点机字长16位,其浮点数格式为:阶码5位(含1位阶符),采用补码表示,尾数11位(含1位数符),采用补码表示,且尾数为规格化形式。已知X=0.1011000011×20.0101,Y=0.0001100000×20.1000,试求X+Y.要求写出详细的
随机试题
A.猪B.人C.两者均可D.两者均不可
第一张尸体识别卡应放置于
根据房屋的完损等级,可以将房屋分为以下几类,正确的是()。
施工单位必须按照工程设计要求、施工技术标准和合同约定,对()进行检验,检验应当有书面记录和专人签字;未经检验或者检验不合格的,不得使用。
下列各项中,能够据以判断非货币性资产交换具有商业实质的有()。
中国新民主主义革命
已知函数f(x)在(一∞,+∞)内具有二阶连续导数,且其一阶导函数f′(x)的图形如图8一1所示,则:曲线y=f(x)的拐点是_____________.
张静是一名大学本科三年级学生,经多方面了解分析,她希望在下个暑期去一家公司实习。为获得难得的实习机会,她打算利用Word精心制作一份简洁而醒目的个人简历,示例样式如“简历参考样式.jpg”所示,要求如下:根据页面布局需要,插入考生文件夹下图片“1.pn
ThisarticlemainlydiscussesaboutthepopularityofChineseinwesterncountries.TheConfuciusInstitutesaimatpromotingt
A、Everybodywillfeelcentered.B、Nobodywillgetbored.C、Nobodywillbeexcluded.D、Everybodywilltalkalot.C
最新回复
(
0
)