在一个有向图中，若存在弧，则在其拓扑序列中，顶点vi，vj，vk的相对次序为（）。

题目

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

相似问题和答案

第1题：

拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，(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。

第2题：

试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。

参考答案：
　　引入一变量level来控制递归进行的层数
　　[算法描述]
　　int visited[MAXSIZE]; //指示顶点是否在当前路径上
　　int level=1;//递归进行的层数
　　int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j
　　是否有路径,是则返回1,否则返回0
　　{
　　if(i==j) return 1; //i就是j
　　else
　　{
　　visited[i]=1;
　　for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--)
　　{ level++;
　　k=p->adjvex;
　　if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径
　　}//for
　　}//else
　　if (level==1) return 0;
　　}//exist_path_DFS

第3题：

在有向无环图中,若存在一条从顶点i到顶点j的弧,则在顶点的拓扑序列中,顶点i与顶点j的先后次序是()。

参考答案：i在j之前

第4题：

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

A.41235

B.43125

C.42135

D.41=325

正确答案：A

第5题：

在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是()。

A.G中有弧

B.G中有一条从Vi到Vj的路径

C.G中没有弧

D.G中有一条从Vj到Vi的路径

正确答案：D

第6题：

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

（57）

A. 包含回路

B. 是强连通图

C. 是完全图

D. 是有向树

正确答案：A

第7题：

在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形可能出现的是()

AG中有弧

BG中有一条从Vi到Vj的路径

CG中没有

DG中有一条从Vj到Vi的路径

参考答案：ABC

第8题：

若有向图中含有一个或多个环,则其顶点间不存在拓扑序列。()

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

参考答案：正确

第9题：

在一个有向图G的拓扑序列中,顶点Vi排列在Vj之前,说明图G中(59)。A.一定存在弧B.

在一个有向图G的拓扑序列中，顶点Vi排列在Vj之前，说明图G中（59）。

A.一定存在弧＜vi,vj＞

B.一定存在弧＜vj,vi＞

C.可能存在vi到vj的路径，而不可能存在vj到vi的路径

D.可能存在vj到vi的路径，而不可能存在vi到vj的路径

正确答案：C
拓扑序列是拓扑排序的产出物。对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。由此可见，如果Vi排列在Vj之前，说明可能存在vi到vj的路径，而不可能存在vj到vi的路径。

第10题：

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

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

答案：C

解析：

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

在一个有向图中，若存在弧，则在其拓扑序列中，顶点vi，vj，vk

题目

相似问题和答案

更多相关问题

相关内容