我要招人

去企业版

首页 > 试题广场 >

若采用邻接矩阵存储一个有向图，且邻接矩阵主对角线以下元素均为

[单选题]

若采用邻接矩阵存储一个有向图，且邻接矩阵主对角线以下元素均为0，则该有向图的拓扑序列（）

```
存在且唯一
```
```
存在但可能不唯一
```
```
不存在
```
```
无法确定
```

查看正确选项

上岸er

这道题答案选B，不选c。题库里另一道同样的题选c，但和b选项一样。

所以看题要看选项

主对角线以下为0说明有向图只有序号小的节点指向序号大的节点，也就是说这个有向图是无环的，所以存在拓扑序列。

然后再举个例子看看是否唯一

（1）

若邻接矩阵为

011

000

那么此时拓扑序列有

1、2、3和1、3、2，所以不唯一

（2）

因为还有拓扑排序唯一的情况，此时邻接矩阵为

010

001

000

此时拓扑序列为1、2、3，唯一

发表于 2022-08-09 09:31:17 回复(0)

勤奋努力学习

0111

0000

0001

0000

这种情况存在拓扑序列且不唯一

发表于 2022-04-14 14:57:44 回复(0)

云云云一飞冲天

这题答案错了，应该选B，即存在但可能不唯一；

拓扑排序的充要条件是有向无环图；

从邻接矩阵的对角线一下元素都为零可以判断出，这个有向图只有顶点i到顶点j（i<j）可能有边，反之肯定没有边，必定是有向无环图，所以必然存在拓扑序列；

然后举个例子说明拓扑序列可能不唯一即可；

如：

0 1 1

0 0 0

这个就不唯一

发表于 2022-08-25 13:50:15 回复(0)

zZZ-1

求解析：怎么判断拓扑序列是否存在？

发表于 2022-07-01 18:46:58 回复(1)

牛客76165061号

为什么不是D，主对角线以下又不包括对角线，如果有自环呢

发表于 2024-03-09 14:49:41 回复(0)

牛客131181223号

以4个顶点为例,邻接矩阵如下:

表示有如下边:

0 -> 1

0 -> 2

0 -> 3

1 -> 2

1 -> 3

2 -> 3

画成图如下:

无论从哪个顶点开始遍历,dfs postorder都是3 2 1 0, reverse之后为0 1 2 3

从这图明显看出来:

要做3,必须先做2
要做2必须先做1
要做1,必须先做0

所以答案选A: 存在且唯一

发表于 2023-10-27 22:49:59 回复(0)

云云云一飞冲天

这题答案错了，应该选B，即存在但可能不唯一；

拓扑排序的充要条件是有向无环图；

然后举个例子说明拓扑序列可能不唯一即可；

如：

0 1 1

0 0 0

这个就不唯一

发表于 2022-08-25 13:50:15 回复(0)

一枚蛋Oops

发表于 2019-11-21 13:33:07 回复(1)

提交观点

问题信息

图

上传者：城市里的养猫者

难度：

8条回答 112收藏 2890浏览

若采用邻接矩阵存储一个有向图，且邻接矩阵主对角线以下元素均为

问题信息

热门推荐

相关试题