首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
admin
2019-08-01
83
问题
对于一个使用邻接表存储的有向图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年,英格兰的《森林宪章》允许平民百姓在王室森林中放牧牲畜、挖掘水渠并从事其他农业活动。颁布该宪章的主要目的在于()
以下不属于泰州学派的哲学思想的是()。
太平天国在1853年冬颁布的纲领性文件是()。
某新石噐遗址发现大量稻谷壳和稻草,红士,防洪水城垣,此遗址可能是
20世纪30年代,美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势,维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。(1)分别画出寻址方式由操作码指出和寻址方式由专用字
设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][O]的存储地址为860,则a[3][5]的存储地址为()。
某工厂有一个仓库可以存放甲、乙两种零部件,甲零件可以存放m件,乙零件可以存放n件,车间A专门生产甲零件,每次1件,每生产1件存放进仓库1件;车间B专门生产零件乙,每次1件,每生产1件存放进仓库1件。总装车间每次从仓库取出2件甲零件、1件乙零件组装成成品,车
随机试题
试回答下列光纤数字传输系统实测项目的相关问题。光接口实测的关键项目有()。
当取不同的构件作机架时,曲柄滑块机构可演化成()种铰链四杆机构。
甲项目收益率的期望值为10%,标准差为10%,乙项目收益率的期望值为15%,标准差为10%,则可以判断()
下列诗作,抒写新时期青年爱国深情的是
对重症胰腺炎最具诊断价值的是
临床上应首先考虑为首选的辅助检查方法是
狭义的德育是指()。
义中提到的“活着的人”与“生活的人”之间最根本的区别是什么:文中提到的李白、杜甫、白居易、苏东坡、贝多芬、梵.高、毕加索,他们是______。
以___________为主体,___________共同发展,是我国社会主义初级阶段的一项基本经济制度。这是由我国___________的状况和发展要求决定的。
阅读下列说明和图,回答问题1至问题3。【说明】某学校的教学系统描述如下。学生信息包括:学号(Sno)、姓名(Sname)、性别(Ssex)、年龄(Sage)、入学年份(Syear)、主修专业(Smajor),其中学号是入学时唯一编定的。
最新回复
(
0
)