首页 > 试题广场 >

G的拓扑序列是：

[不定项选择题]
已知有向图G=（V，E）其中V={V1，V2,V3，V4，V5，V6,V7}
E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V2,V6>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},
则G的拓扑序列是：（） 
  • V1, V4，V2，V6, V3，V5，V7
  • V1，V2，V3，V4, V5，V6，V7
  • V1，V3, V4，V2，V6，V5，V7
  • V1，V3，V4, V6，V2, V5，V7
添加回答
推荐
Miner_Sty头像 Miner_Sty
不断选取入度为0的节点，然后将其后继节点的入度减一，依次计算。
编辑于 2016-04-28 09:13:26 回复(8)
RockMan头像 RockMan
         http://baike.baidu.com/link?url=1nDvMOujJ-coWDfJFRSqO68bBgKMaDeu3btcnjLwD6WSAZ5dQFC4Bq-ZQOMuXJo8-SRDmnq3GPmkLzMKOK_Z9a
解题要点：
    1.明白何为拓扑排序，其特点为什么？  以及排序结果是否唯一？
           对一个 有向无环图 (Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。排序结果不唯一。
    2.如何完成拓扑排序。
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列
    3.拓扑排序及应用。
        拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。再进行多线程程序中可能会用到，将多线程单线程化。.....

发表于 2015-09-11 15:34:48 回复(1)
青山崖野头像 青山崖野
v6必须在v2,v3,v4都出后，入度才会为0，所以不可能是AD选项
发表于 2017-07-06 22:56:10 回复(0)
牛牛12315头像 牛牛12315
画出有向图，可知要使v5的入度为0，必须撤掉v2v3，则v5必在v2v3后面，同理v6必在2、3、4后面，故AD排除
发表于 2015-10-01 09:42:43 回复(0)
未来的搬运工头像 未来的搬运工
有个简单的方法，根据拓扑排序概念（对于从顶点u到顶点v的每个有向边uv，u在排序中都在v之前）
由<V2,V6>,<V3,V6>可知V6在V3和V2后面，然后答案就出来了=w=，BC
编辑于 2017-12-14 09:50:51 回复(0)
zhangxus头像 zhangxus

求拓扑序列步骤：

    1,画出有向图，找到一个入度为0的点作为拓扑序列的第一个点

    2，把该点和该点所有的边从图中删去

    3，再在新的图中选择一个入度为0的点作为拓扑系列的第二个点

...以此类推，如果在所有节点尚未删去时找不到入度为0的点则说明剩余节点存在环路，不存在拓扑序列

发表于 2019-08-01 16:24:46 回复(0)
yql头像 yql
对于任意一条有向边，保证前面顶点在序列的前面。
        用排除法，
        A    <V3,V6>不符合。
        D    <v2,v6v>不符合。
BC符合
发表于 2015-09-15 11:31:02 回复(0)
未知账号头像 未知账号
拓扑序列的求解方法：
(1)、找到一个没有后继的顶点(如果有一条边从A指向B,那么B是A的后继)。
(2)、从图中删除这个顶点，在列表的前面插入顶点的标记。
(3)、重复步骤1和2.直到所有的顶点都从图中删除。这时列表显示的顶点顺序就是拓扑排序的结果。
发表于 2015-09-10 23:45:55 回复(0)
就这样吧x头像 就这样吧x
首先拿出入度为0的，再一次就是它的出边，依此顺序执行，则为V1、（V2、V3、V4）、（V5、V6）、V7
括号内的可以调换顺序
发表于 2016-09-05 22:30:03 回复(0)
不拿到好offer不改名头像 不拿到好offer不改名
不简单
发表于 2023-05-09 10:57:43 回复(0)
泽思头像 泽思
根据给的E顺序，可得到有向图G如下（图1）：



获取拓扑结构：（不断选取入度为0的节点，然后将其后继节点的入度减一，依次计算。）
（1）首先找：只有指向其他结点，没有指向自己的结点，（选取入度为0的节点）
如：V1结点；即起点；（V1）

（2）然后将V1删去结点和相关路径删去；得到图2；（删去选取的度为0的结点，其后继节点的入度减1）

（3）对图二进行（1）操作，找到结点V2、V3、V4；这三个结点都可以作为新起点；（选取入度为0的节点）
这里以V3为例；（V1，V3）

（4）删去V3结点和相关路径，在新图找到可作为起点的V2,V4；（选取入度为0的节点）
结合C、D选项，继续删去V4；（V1，V3，V4）

（5）此时若删去V2，对其他结点路径无影响；若删除V6结点，则存在V2的一个路径指向出现问题；
故选项D错；（V1，V3，V4，V2）

（6）如上操作，继续删除结点和相关路径（不断选取入度为0的节点，然后将其后继节点的入度减一）；
可证C选项正确；

同理可证A选项错误，B选项正确；

编辑于 2021-06-01 15:25:10 回复(0)
天尊墨宇头像 天尊墨宇
选BC

求拓扑序列步骤：

    1,画出有向图，找到一个入度为0的点作为拓扑序列的第一个点

    2，把该点和该点所有的边从图中删去

    3，再在新的图中选择一个入度为0的点作为拓扑系列的第二个点

...以此类推，如果在所有节点尚未删去时找不到入度为0的点则说明剩余节点存在环路，不存在拓扑序列

发表于 2020-08-09 10:57:25 回复(0)
黑闪⚡头像 黑闪⚡
竟然是多选，mmp。。。
发表于 2020-04-25 21:36:30 回复(0)
_向offer冲锋-头像 _向offer冲锋-

根据题目可以画出图，拓扑排序过程中，v2，v3，v4应该是在一起的

发表于 2020-03-03 07:34:16 回复(0)
詹俊朗头像 詹俊朗
直接排除法。。。
发表于 2019-03-13 10:49:07 回复(0)
大脸盘纸头像 大脸盘纸
拓扑排序 给定一副有向图，将所有顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素。
发表于 2017-01-04 15:51:16 回复(0)
-狂战-头像 -狂战-
拓扑排序规则带来的必然结果：若存在u到v的路径，则在 拓扑排序 序列中u一定在v的前边  
编辑于 2016-08-08 12:02:26 回复(0)
tylk_2016头像 tylk_2016
对一个有向图进行拓扑排序，就是将有向图中的所有顶点排成一个线性序列，使得对有向图中任意一对顶点 u 和 v ，如果< u,v >是有向图中的一条边，则顶点 u 在该线性序列中出现在顶点 v 之前，这样的线性序列称为满足拓扑排序的序列，简称为拓扑排序。
有向图的拓扑排序算法如下:
1. 在有向图中选择一个没有前驱的顶点，并把它输出；
2. 从有向图中删去该顶点以及与它相关的有向边。
重复上述两个步骤，直到所有顶点都输出，或者剩余的顶点中找不到没有前驱的顶点为止。在前一种情况下，顶点的输出序列就是一个拓扑序列；后一种情况则说明有向图中存在回路，如果有向图中存在回路，则该有向图中一定无法得到一个拓扑序列。
发表于 2016-01-20 12:10:45 回复(0)
yang.li头像 yang.li
这个题得明白什么是拓扑排序，凭借几句解析会让你更加难以理解，百度找个ppt课件看看(数据结构)
发表于 2015-09-13 09:27:07 回复(1)
残酷天使的行动纲领头像 残酷天使的行动纲领
拓扑排序的规则是: 对有向无环图的路径<u,v>, u总是排在v的前面.

可以使用队列实现拓扑排序:
1.计算所有节点的入度
2.将入度为零的节点入队
3.将队列中的节点出队, 输出该节点, 并让该节点的后继节点入度-1, 如果后继节点的入度变为0, 则将后继节点入队, 直到队列为空, 输出的序列即为拓扑排序序列

V1入度为0, 记为V1(0),  后继为V2(1), V3(1), V4(2), 对于A选项, V1出队, 则V2 3 4的入度-1, 此时V4(1), 入度不为0, 不可能入队, 更不可能出队输出, A错. 其他选项类推.
编辑于 2015-09-11 11:05:44 回复(0)
提交观点

问题信息

图
来自：2016CVTE校招在...
难度：
20条回答 16947浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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