首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
admin
2019-08-01
52
问题
对于一个使用邻接表存储的有向图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
学硕统考专业
相关试题推荐
1946年初,“美国计划将中共以一种类似西欧共产党所占的地位,纳入一个实际政体的政治和军事范围之内,敌对的两党共同参加一个以蒋介石为首的经过改组的联合政府”。材料反映出美国的意图是()
达芬奇、米开朗基罗、拉斐尔称为“文艺复兴三杰",与启蒙思想家相比,他们
下列哪部戏剧不是曹禺的作品()。
东汉末期的农民起义出现的新特点是()。
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
就绪队列中有n个进程等待使用一个CPU,那么,如果采用不同的调用算法,就有()种调度顺序。
某DRAM芯片内部存储元排列成1024.×1024的矩阵,且已知其存取周期为0.1μs,最大刷新间隔为2ms。当采用异步刷新方式时,死时间()。
写出单总线结构计算机中指令MOVER1,R2(含义是将寄存器R1中内容写入寄存器R2中)的操作步骤。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,则最后一个结点下标为k(
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
随机试题
初二(2)班的女生晓芳和小敏是好朋友,由于晓芳上周休病假,刚到学校就遇上体育课。在课的上半段进行耐久跑时.晓芳觉得头晕、胸口憋闷、呼吸急促、下肢沉重,有一种不想坚持跑下来的感觉,但在小敏的鼓励下还是跑到了终点。在课的下半段进行蛙跳练习时,晓芳的积极性不高
从中华传统美德的角度看,“修身、齐家、治国、平天下”强调的是要加强道德修养,注重道德践履。以下与其含义一致的有()
誓
场地平整是指按设计图示尺寸以建筑物首层面积计算,其适用于()。
影响边坡稳定性的因素有内在因素与外在因素两个方面。内在因素有组成边坡()等,它们常常起着主要的控制作用。
背景资料A公司承包某项目的机电安装工程,工程主要内容有:建筑给水排水、建筑电气工程、通风空调工程和建筑智能化工程等。合同约定:电力变压器、空调机组、配电柜、控制柜和水泵等设备由业主采购;阀门、灯具、风口、管材、电线电缆等由A公司采购。A公司因人力资
It’softensaidthatthemarkofacivilisedsocietyishowittreatsitsmostvulnerablecitizensintimesofausterity.Andin
在窗体上画两个滚动条,名称分别为Hscro111、Hscro112;六个标签,名称分别为Labell、Labe12、Labe13、Labe14、Labe15、Labe16,其中标签Labe14~Labe16分别显示“A”、“B”、“A*B”等文字信息
有关系Students(学号,姓名,性别,专业),下列SQL语句中有语法错误的是
WhatdoesJohnmean?
最新回复
(
0
)