首页 > 试题广场 >

若用邻接矩阵存储有向图，矩阵中主对角线以下元素均为零，则关于

[单选题]

若用邻接矩阵存储有向图，矩阵中主对角线以下元素均为零，则关于该图拓扑序列的结论是（）。

找工作的饼干

“矩阵中主对角线以下元素均为零”，说明只能有序号小的元素指向序号大的元素，不能形成环，所以拓扑序列存在。

不唯一的情况，比如是非连通图，有多种拓扑排序方式。

唯一的情况：

因为对于有向图而言，邻接矩阵的第i列非零元素的个数，表示顶点i的入度。

根据题目要求第一列所表示的结点是没有前驱结点的，可以作为第一个元素输出；

只需要满足除第一列外的其他列存在非零元素，拓扑排序是唯一的。

图：

编辑于 2021-04-06 22:14:55 回复(6)

牛客368281515号

题目只说主对角线及以下是零，没说上三角的元素都是非零的，因此存在但是不唯一

编辑于 2021-11-28 23:11:52 回复(1)

牛客274233608号

选A，因为说明在此有向图中，1为起点，n为终点。则1号顶点入度为o，先访问，2的前驱只有1，其他的节点都有前驱。根据塔普排序的规则，每次弹出一个入度为0的顶点，而且这种情况下每次都只有一个顶点入度为0，所以访问顺序只可能是1，2,3，。。。。N

发表于 2020-11-22 18:17:24 回复(0)

Xechos

无环

发表于 2020-11-08 19:10:51 回复(0)

天尊墨宇

选C
邻接矩阵存储有向图且主对角线以下的元素均为零，说明在此有向图中，1为起点，n为终点。任何一个顶点都不能到达比其号码小的顶点。在这种有向图中拓扑序列是存在的，但是可能唯一，也可能不唯一。例如，只有两个顶点的有向图，其拓扑序列就唯一。但是，三个顶点的有向图中拓扑序列就可能不唯一了。

发表于 2020-07-12 10:16:56 回复(0)

DonMuv

C，这种情况仅代表没有环

发表于 2019-11-05 10:08:43 回复(0)

幻想舞蛇

C .

邻接矩阵存储有向图且主对角线以下的元素均为零，说明在此有向图中，1为起点，n为终点。任何一个顶点都不能到达比其号码小的顶点。在这种有向图中拓扑序列是存在的，但是可能唯一，也可能不唯一。例如，只有两个顶点的有向图，其拓扑序列就唯一。但是，三个顶点的有向图中拓扑序列就可能不唯一了。

发表于 2019-10-12 14:40:21 回复(0)

提交观点

问题信息

图

上传者：城市里的养猫者

难度：

7条回答 6收藏 6962浏览