首页 > 试题广场 >

已知有向图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
查看正确选项
添加回答
Linkang头像 Linkang
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。
（1）每个顶点出现且只出现一次；
（2）若A在序列中排在B的前面，则在图中不存在从B到A的路径。

此拓扑排序的思想是：

（1）从有向图中选取一个没有前驱的顶点，并输出之；

（2）从有向图中删去此顶点以及所有以它为尾的弧；
第一步： 删除V1，
第二步： 可选的没有前驱的点有V2，V3，V4
第三步 ：假如下一步选择的是V3，则删除V3，可选的有V2，V4
第四步： 假如选择的是V2，则删除V2, 可选的有V4，V5（所以答案B错误了）
第五步： 假如选择的是V4，则删除V4，可选的有V5，V6
第六步： 假如选择的是V5，则删除V5， 剩余就是V6->V7了
所以排序为V1，V3，V2，V4，V5，V6，V7

根据以上思路，可以推出只有答案A才是对的。

编辑于 2017-06-19 22:36:47 回复(3)
东东xxdded头像 东东xxdded
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。 
（1）每个顶点出现且只出现一次；
（2）若A在序列中排在B的前面，则在图中不存在从B到A的路径。

此拓扑排序的思想是：

（1）从有向图中选取一个没有前驱的顶点，并输出之；

（2）从有向图中删去此顶点以及所有以它为尾的弧；
第一步： 删除V1，
第二步： 可选的没有前驱的点有V2，V3，V4
第三步 ：假如下一步选择的是V3，则删除V3，可选的有V2，V4
第四步： 假如选择的是V2，则删除V2, 可选的有V4，V5（所以答案B错误了）
第五步： 假如选择的是V4，则删除V4，可选的有V5，V6
第六步： 假如选择的是V5，则删除V5， 剩余就是V6->V7了
所以排序为V1，V3，V2，V4，V5，V6，V7

根据以上思路，可以推出只有答案A才是对的。
发表于 2017-07-27 16:55:12 回复(0)
提交观点

问题信息

图
上传者：Letitia
难度：
2条回答 18697浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号