对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减1，并对其未访问的、入度为0的邻接到的顶点进行递归。写出在遍历图的同时进行拓扑排序的算法。

admin2019-08-15 63

问题对于一个使用邻接表存储的有向图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结束 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)； } 提示：此题考查的知识点是图的遍历。对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点v出发遍历，在dfS(v)结束之前，出现从顶点u到顶点v的回边，图中必存在环。由于dfs产生的是逆拓扑排序，故设一类型是指向邻接表的边结点的全局指针变量final，在dfs函数退出时，把顶点v插入到final所指的链表中，链表中的结点就是一个正常的拓扑序列。

解析

转载请注明原文地址:https://kaotiyun.com/show/udCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

国民党政府被彻底打垮的战役是()。

中国革命必须走农村包围城市最后夺取政权这样一条道路，主要取决于()。

“神之于质，犹利之于刃；形之于用，犹刃之于利。利之名非刃也，刃之名非利也；然而舍利无刃，舍刃无利。未闻刃没而利存，岂容形亡而神在?”这段话体现的观点是()。

()是清中叶扬州画家的著名代表，他们既不墨守成规，又不脱离优秀传统，成为我国绘画艺术史上的一个新流派。

相对于单一内核结构，采用微内核结构设计实现操作系统具有诸多好处，但是，()并不是微内核的优势。

进程从运行状态转换为就绪状态的可能原因是()。

若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。

下列属于制约股利分配的公司因素的有()。

环磷酰胺的主要适应证是

A．黏液血便B．大便次数和便血程度C．腹痛程度D．腹胀反映溃疡性结肠炎病情的轻重

霍乱轻型者治疗应霍乱中型以上者治疗应

关于老年人用药A、链霉素B、利血平C、噻嗪类D、可的松类E、吲达帕胺不宜用于糖尿病老年患者的是

组合结果数据在不同风险管理领域的一致应用，是商业银行最终实现经济资本计量的关键所在。()

下列各项中，属于有效民事行为的有（）。

没有抽象的真理，真理总是具体的。这一思想可以理解为()。

Excel工作表D列保存了18位身份证号码信息，为了保护个人隐私，需将身份证信息的第3、4位和第9、10位用“*”表示，以D2单元格为例，最优的操作方法是()。