首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
admin
2019-08-01
61
问题
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。
写出在遍历图的同时进行拓扑排序的算法。
选项
答案
算法 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; //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结束 intdfx_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://www.kaotiyun.com/show/QVCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
比较文艺复兴时期人文主义思想和宗教改革思想的异同。
论述屋大维的元首政制的统治特点。
资产阶级改良道路行不通,资产阶级共和国方案夭折,其共同原因在于()。①中国封建势力的强大②帝国主义列强的直接破坏③资产阶级的软弱妥协④没有充分地发动人民群众
提出电磁感应定律的是物理学家()。
北宋在统一南方割据势力的过程中特设(),把征南所得的财富统一存放,以作日后恢复幽燕之费。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
某计算机的Cache共有16块,采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节,按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
在机器数中,正数的符号位用“1”表示的是()。
随机试题
男性,44岁。因高处坠落多发性骨折并发急性呼吸窘迫综合征(ARDS),骨折已经过处理,正接受人工气道和呼气末正压机械通气治疗。为预防肺部感染,针对外源性感染途径,下列措施以哪一项最重要
溃疡性结肠炎的临床表现下列哪项是错误的
甲失手将乙打成重伤,甲应当赔偿给乙的费用有()。
思维按其内容分为()。
下列哪一部位或神经元受损可导致舞蹈病
宏观审慎监管
Arepasswordsoutdated?It’sstartingtoseemlikeit.Everybodyhatesthem,andnobodycanrememberalltheonesthey’ve【C1】___
关于计算机病毒的传播途径,以下说法不正确的是()。
23OakAvenueManchesterDearSirorMadam,
ThereissomethingbadlywrongwiththewaystandardsforschoolsciencebeingsetintheUS.WhentheTexasStateBoardofEduc
最新回复
(
0
)