首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
admin
2019-08-01
67
问题
对于一个使用邻接表存储的有向图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://kaotiyun.com/show/QVCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:明朝推行一条鞭法中“一”的内容是()
二战后世界经济走向统一的过程中,仍然存在着多样性,出现了“两种体系、三种国家”,下列不属于社会主义国家经济类型的是()。
中国第一个资产阶级革命团体兴中会建立的时间是()。
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
以下()协议完成了从网卡到IP地址的映射。
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
驱动调度算法中,()算法可能会随时改变移动臂的运动方向。
随机试题
下列哪项可引起右室压力负荷过重
传动轴上的防尘罩应配备齐全,并用卡箍紧固,两只卡箍的锁扣应错开_______装配。
G-M直流调速系统可以允许转矩范围内()象限运行的系统。
资本主义银行利润在______、_______、_______、_______。
纤维结构不良的特点不包括
A.120/70mmHg以下B.125/75mmHg以下C.130/80mmHg以下D.140/90mmHg以下E.140/85mmHg以下慢性肾小球肾炎患者,尿蛋白<1g/d,血压应控制在
治疗汗证营卫失调证的首选方剂是
王某向当地的工商局申请工商登记,工商局因其不符合法定条件而不予登记,王某对该行政许可的决定不服,向当地人民法院提起行政诉讼的权利体现了()。
2015年5月,中国居民企业甲以其持有的一处房产向另外一家居民企业乙进行投资,双方约定投资价款5000万元,该房产原值2000万元,取得的货币性资产转让所得3000万元,不考虑其他因素,假设甲企业最大限度的享受现行非货币性资产对外投资的企业所得税政策,则2
下列有关偿债能力分析的说法中,正确的有()。
最新回复
(
0
)