首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
admin
2019-08-01
50
问题
对于一个使用邻接表存储的有向图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
学硕统考专业
相关试题推荐
1927年在《中共“八七”会议告全党党员书》中提出了“土地国有”的主张;1929年6月,《红四军司部政治部布告》中规定:“田归耕种的农民所有”;1931年中共制定的土地革命路线明确指出“变建土地所有制为农民土地所有制”。上述材料表明中共()。
在加强对边疆地区的治理方面,明清两朝推行的相同措施是()。
西周的官僚制度已经相当完备,官僚机构庞杂,职官名目繁多。周王室的官僚机构分为两大系统,分别是()。
前期的新文化运动不能给灾难深重的中国指明真正的出路,主要是由于()。
苏联实行新经济政策和美国推行罗斯福新政的相似点是()。①面临极为困难的经济形势②国家颁布政策法令强制干预经济③最主要内容是调整和复兴工业④通过发展商品生产来恢复农业
1936年,张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成
拿内存加上外存容量之和与虚拟存储空间相比,其大小关系是()。
设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][O]的存储地址为860,则a[3][5]的存储地址为()。
一台模型机共有7条指令,主频25MHz,各指令的使用频率与CPI如下表所示,该机有8位和16位两种指令字长,采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型,16位字长指令为寄存器一存储器(R—M)二地址变址类型(地址码范围在-128
“乘法减少”和“加法增大”备用在什么情况下?
随机试题
信知生男恶,________。
WhenIspentthesummerwithmygrandpainWarwick,hesentmetoMissBee’sstore.【C1】______thecounterwasMissBee.Apairo
下列哪些检查可提示胎儿发育成熟()
下列哪项不是诊断石棉肺的依据
下列有关答复政府信息公开申请的说法正确的是:()
同步建设原则是指统筹场区总平面布置规划,( )。
交通安全设施除里程标、百米标和公路界碑以外,还包括()。
关于我国社会主义初级阶段的说法,正确的有()。
下列对肯定性训练理解不正确的是()。
Tolearnwithsuccessisnotaverydifficulttaskofsomefundamentalprinciples【C1】______tobeitsbases.【C2】______discussi
最新回复
(
0
)