首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
admin
2019-08-01
74
问题
对于一个使用邻接表存储的有向图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
学硕统考专业
相关试题推荐
针对“海内新定,同姓寡少”的特点,西汉统治者采取了下列哪一项措施?()
世界上第一个工农苏维埃政府成立后采取的()措施最能反映当时俄国人民的迫切愿望
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:乾隆年间的税种有()
美国主张建立国际联盟的主要目的是()。
太平天国在1853年冬颁布的纲领性文件是()。
中国第一个资产阶级革命团体兴中会建立的时间是()。
中国共产党在下列哪次会议上规定了党的最高纲领和最低纲领?()
1980-1987年撒哈拉以南非洲人均国民生产总值增长率为-2.9%。大部分国家经济急剧下滑,非洲的80年代被称“为失去发展的十年”。出现这现象关键原因在于这些国家
“两个凡是”
在机器数中,正数的符号位用“1”表示的是()。
随机试题
患者平素嗜食肥甘,近1周来出现小便浑浊,上有浮油,尿道热疼痛,口渴苦,苔黄腻,脉濡数,其治法为
细菌内毒素的特征是
患者,男性,60岁。急性广泛前壁心肌梗死,经治疗疼痛缓解,但患者烦躁不安,血压80/60mmHg,脉搏120次/分,尿量20ml/h。此时患者的情况属于
我国决策住房公积金管理的机构是()。
日记账一般采用的账簿格式是()。
某有限责任公司注册资本为100万元,股东人数为4人,董事会成员为9人,监事会成员为3人。该公司出现下列情形应当召开临时股东会的有()。
事业单位长期投资的成本包括()。
1927年大革命失败后,白色恐怖笼罩着全国城乡,许多共产党员和党的领导干部被捕、被杀,同年8月7日,中共中央在汉口秘密召开紧急会议,史称八七会议。关于八七会议,下列说法正确的有
设y=f(χ)为区间[0,1]上的非负连续函数.(1)证明存在c∈(0,1),使得在区间[0,c]上以f(c)为高的矩形面积等于区间[c,1]上以y=f(χ)为曲边的曲边梯形的面积;(2)设f(χ)在(0,1)内可导,且f′(χ)>-,
Mostpeoplewhotravellongdistancecomplainofjetlag.Jetlagmakesbusinesstravelerslessproductiveandmoreprone【C1】____
最新回复
(
0
)