拓扑排序的主要功能是什么?对于一个存在拓扑序列的有向图,通过拓扑排序得到的拓扑序列是否惟一?

题目

拓扑排序的主要功能是什么?对于一个存在拓扑序列的有向图,通过拓扑排序得到的拓扑序列是否惟一?

如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

拓扑排序算法仅适用于有向无环图。()


参考答案:错误

第2题:

任何有向图的顶点都可以排成拓扑有序序列,而且拓扑序列不唯一。()

此题为判断题(对,错)。


参考答案:错误

第3题:

拓扑序列是无环有向图中所有顶点的一个线性序列,图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系,(52)为下图所示有向图的一个拓扑序列。

A.1 2 3 4 5 6 7

B.1 5 2 6 3 7 4

C.5 1 2 6 3 4 7

D.5 1 2 3 7 6 4


正确答案:B
解析:本题考查有向图的应用。
  拓扑排序是将有向图中所有顶点排成一个线性序列的过程,并且该序列满足:若在图中存在从顶点vi到vj有一条路径,则在该线性序列中,顶点vi必然在顶点cj之前。
  对有向图进行拓扑排序的方法如下:
  ①在有向图中选择一个入度为零(没有前驱)的顶点且输出之;
  ②从网中删除该顶点及从该顶点出发的所有弧;
  ③重复上述两步,直至图中不存在入度为零的顶点为止。
  对题目中所给的有向图进行拓扑排序的顶点序列为:5126374、5126734、1526374、 1526734。

第4题:

拓扑序列是无环有向图中所有顶点的一个线性序列,图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系。对于图中的有向图, ( ) 不是其的一个拓扑序列。

A.1526374
B.1526734
C.5123764
D.5126374

答案:C
解析:
拓扑序列是将有向图中所有顶点排成一个线性序列,并且该序列满足:若在图中存在从顶点Vi到Vj的路径,则在该线性序列中,顶点i必然在顶点Vj之前。对有向图进行拓扑排序的方法如下:① 在有向图中选择一个入度为零(没有前驱)的顶点且输出之:② 从有向图中删除该顶点及从该顶点出发的所有弧;③ 重复上述两步,直至图中不存在入度为0的顶点为止。对于图3-4所示的有向图,进行拓扑排序的顶点序列有:5126374、5126734、1526374和1526734。而选项C的"5123764"不是其中的一个拓扑序列。

第5题:

下面哪个序列不是此图的一个拓扑排序()

A.ebfgadch

B.aebdgfch

C.adchebfg

D.Aedbfgch


正确答案:C

第6题:

对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。()

此题为判断题(对,错)。


正确答案:正确

第7题:

对于图4-1所示的有向图G,写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈,写出函数TopSort执行后得到的拓扑序列。


正确答案:队列:vl、v2、v5、v4、v3、v7、v6 栈:v1、v2、v5、v4、v7、v3、v6
队列:vl、v2、v5、v4、v3、v7、v6 栈:v1、v2、v5、v4、v7、v3、v6 解析:首先根据原图,可以得出本题中只有V3和V7是同时入队或入栈的。
[*]

第8题:

● 拓扑排序是指有向图中的所有顶点排成一个线性序列的过程,若在有向图中从顶点vi到vj有一条路径,则在该线性序列中,顶点 vi 必然在顶点 vj之前。因此,若不能得到全部顶点的拓扑排序序列,则说明该有向图一定 (57)

(57)

A. 包含回路

B. 是强连通图

C. 是完全图

D. 是有向树


正确答案:A

第9题:

拓扑序列是有向无环图中所有顶点的一个线性序列,若有向图中存在弧或存在从顶点v到w的路径,则在该有向图的任一拓扑序列中,V一定在w之前。下面有向图的拓扑序列是( )

A.41235

B.43125

C.42135

D.41=325


正确答案:A

第10题:

已知有向图G=(V,A),其中V={a,b,C,d,e},A={<a,b>,<a,c>,<d,c>,<d,e>,<b,e>,<c,e>},对该图进行拓扑排序,下面序列中()不是拓扑排序

A.a,d,c,b,e
B.d,a,b,c,e
C.a,b,d,c,e
D.a,b,c,d,e

答案:D
解析: