首页 > 试题广场 >

已知有向图G=(V,E),其中V={V1,V2,V3,V4,

[单选题]
已知有向图G=(V,E),其中V={V1 ,V2 ,V3 ,V4 ,V5 ,V6 ,V7 },E={(V1 ,V2 ),(V1 ,V3 ),(V1 ,V4 ),(V2 ,V5 ),(V3 ,V5 ),(V3 ,V6 ),(V4 ,V6 ),(V5 ,V7 ),(V6 ,V7 )},G的拓扑序列是()
  • V1,V3,V4,V6,V2,V5,V7
  • V1,V3,V2,V6,V4,V5,V7
  • V1,V3,V4,V5,V2,V6,V7
  • V1,V2,V5,V3,V4,V6,V7
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之;
(2) 从网中删除此顶点及所有出边
循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列
发表于 2015-07-05 21:08:57 回复(2)
啥头像
发表于 2015-12-08 12:26:46 回复(0)

设有向图G中有向边的集合E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},则该图的一种拓扑序列为?

根据集合E,顶点1发出两个弧指向2、4,顶点2发出弧指向3,顶点4发出两个弧指向2、3.
拓扑序列选择无前驱顶点输出,输出后删除该顶点及其发出的弧,直到无顶点可输出时停止。
故其一种拓扑序列为:1,4,2,3

所以,按照这个方法即可得出拓扑序列

发表于 2015-04-01 20:26:44 回复(1)
A只是其中 一种正确拓扑排序,一个有向无环图的拓扑排序可能有多个
发表于 2015-08-12 11:12:00 回复(0)
把图画出来后,选项中出现一个删掉一个,如果发现需要删掉的元素仍有前驱存在,则说明错误。
发表于 2018-01-26 09:27:38 回复(0)

在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件:

  1. 每个顶点出现且只出现一次。
  2. 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图(DAG)才有拓扑排序,非DAG图没有拓扑排序一说。

发表于 2016-03-14 16:04:28 回复(0)
拓扑排序常用来确定一个依赖关系集中,事物发生的顺序。拓扑排序得出的线性序列,只要能满足排在前面的任务先完成即可,例如V1→V2,序列中只要V1在V2前面即可(所以得出的序列可能不唯一)。


结合图进行拓扑排序,满足下面条件即可:
    • V1在V2,V3,V4前面
    • V2,V3均在V5前面
    • V3,V4均在V6前面
    • V5,V6均在V7前面
    A项 V 1 ,V 3 ,V 4 ,V 6 ,V 2 ,V 5 ,V 7 正好满足要求,其它项都不满足,选A。
    编辑于 2016-07-29 20:52:12 回复(6)
    a
    发表于 2019-05-02 11:14:19 回复(0)
    哦哦。。。。拓扑排序常用来确定一个依赖关系集中,事物发生的顺序。拓扑排序得出的线性序列,只要能满足排在前面的任务先完成即可,例如V1→V2,序列中只要V1在V2前面即可(所以得出的序列可能不唯一)。


    结合图进行拓扑排序,满足下面条件即可:
    • V1在V2,V3,V4前面
    • V2,V3均在V5前面
    • V3,V4均在V6前面
    • V5,V6均在V7前面
    A项 V 1 ,V 3 ,V 4 ,V 6 ,V 2 ,V 5 ,V 7 正好满足要求,其它项都不满足,选A。
    发表于 2016-08-22 15:52:41 回复(0)
    A吧 必须节点的入度为0才能输出吧,也就是5 要在2 3之后输出 6要在 3 4 之后输出 7要在5 6 都输出之后才能输出
    发表于 2016-07-29 15:17:09 回复(0)
    那D应该也对着呢,为什么不对?
    发表于 2015-09-02 12:26:06 回复(2)
    为什么B是错误的?
    发表于 2015-09-01 16:30:53 回复(2)