首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 写出在遍历图的同时进行拓扑排序的算法。
admin
2019-08-01
40
问题
对于一个使用邻接表存储的有向图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
学硕统考专业
相关试题推荐
中国政府第一次公开提出和平解决台湾问题的方针是在()。
试述马丁.路德宗教改革思想的主要内容。
下列人民起义不是发生在阿拔斯王朝时期的是()。
()是二战后一个调整各国贸易关系的法律框架,又是一个进行多边贸易谈判、争夺市场的场所,还是一个调解和解决争议的机构。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
若某浮点机基数为4,尾数采用补码表示,则该浮点机的规格化尾数形式为()。
著名的网络OSI七层模型是由()组织提出来的。
某计算机的Cache共有16块,采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节,按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
CSMA/CA是如何实现“冲突避免”的?
随机试题
A.胆B.小肠C.大肠D.胃具有贮藏精气的作用
断肾血管平滑肌脂肪瘤主要的诊断依据是
氰化物中毒的特效解毒剂是
从投资者整体的角度出发,以投资者的出资额作为计算基础,把借款本金偿还和利息支付视为现金流出,用以计算资本金财务内部收益率、财务净现值等评价指标,考察项目资本金的盈利能力的报表是()。
[2008年第4题]可行性研究报告的编制费应属于总概算中的哪一项费用?
根据法律是否赋予特定合同名称并设有专门规范,合同可以分为()。
根据外商投资企业法律制度的规定,中外合作经营企业发生的下列事项中,不必由董事会(或者联合管理委员会)出席会议的董事(或者委员)一致通过的有()
谈谈课堂提问应注意什么?
下列画家和其代表作对应正确的是()。
何谓禅宗?它的流传对中国文化产生了哪些重要影响?
最新回复
(
0
)