首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义
admin
2019-08-01
36
问题
对于一个使用邻接表存储的有向图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
学硕统考专业
相关试题推荐
第三次科技革命初期,苏联领先于美国的新兴科学技术成就是()。
()是宋代为支付军政费用而筹措的一宗款项。同时又是各地为筹措这项经费而加征的苛捐杂税的总名称
以下不属于泰州学派的哲学思想的是()。
下列()的社会思想突出表现为“仁”。
1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
1978年直接领导和发动真理标准问题讨论的中央领导人是()。
抗战时期,国民政府一直没有放弃适当条件的对日妥协,于是,中日之间开始秘密接触,日本称之为()
1980年1月,邓小平在《目前的形势和任务》提出的中国人民长期奋斗的三件大事是()。
随机试题
基数效用理论在推导消费者需求曲线时,是以边际效用递减规律和()为基础。
马克思主义哲学同各门具体科学的关系属于
肾脏的替代治疗包括
小柴胡汤中和解少阳的药对是
在板式塔中,筛板塔的特点有()。
以下( )情况不宜安排路基的雨期施工。
假设某只股票连续四年的每股收益分别为:6.2元、7.4元、8.5元和5.5元,那么该股票这四年每股收益的几何平均数为()。
根据1988年《巴塞尔资本协议》的规定,商誉应从核心资本中扣除的比例是()。
(2016·河南)结构主义课程论是以结构主义心理学为基础的课程理论,其代表人物是美国教育家杜威和布鲁纳。()
Agoodmarriagemeansgrowingasacouplebutalsogrowingasindividuals.Thisisn’teasy;marriagehasalwaysbeendifficult.
最新回复
(
0
)