首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
admin
2019-08-01
77
问题
对于一个使用邻接表存储的有向图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
学硕统考专业
相关试题推荐
试析巴以冲突的历史根源。
简述罗马共和国衰亡的原因。
唐朝对外关系呈现出前所未有的盛况,其原因不包括()
对20世纪20年代德国经济复兴的原因表述不准确的一项是()。
太平天国在1853年冬颁布的纲领性文件是()。
世界天文史上最早实地测量子午线的记录是由谁进行的?()
制瓷业是光彩夺目的一个手工业部门,北宋的制瓷业的重心在黄河流域和中原地区。回答问题:()创于唐,盛于北宋,以白瓷著名,为宋代印花白瓷的精品
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
文件系统的主要目的是()。
随机试题
MicrosoftWindows7系统自带的上网浏览器为_______。
多用醋制的中药为
太阳中风证的病机是
医务人员对开展母乳喂养的母亲给予鼓励,属于
下列行为中属于能够发生私法效果的默示的意思表示的是:()
“其他债权投资”科目借方的期末余额,反映企业以公允价值计量且其变动计入其他综合收益的金融资产的公允价值。()
建国70年来我国经济社会发展建设取得了巨大成就。对此,下列说法正确的是()。
设函数y=y(x)由方程确定,则=().
构成计算机信息系统的部件有很多。Ⅰ.数据库子系统Ⅱ.模型库子系统Ⅲ.知识库子系统Ⅳ.方法库子系统Ⅴ.对话子系统以上部件中,在传统的决策支持系统结构中,必不可少的三个部件是()。
WhatmakesAmericansspendnearlyhalftheirfooddollarsonmealsawayfromhome?TheanswerslieinthewayAmericanslivetod
最新回复
(
0
)