首页 > 试题广场 >

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

[单选题]

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

  • 存在且唯一
  • 存在但可能不唯一
  • 不存在
  • 无法确定
查看正确选项
添加回答
上岸er头像 上岸er
这道题答案选B，不选c。题库里另一道同样的题选c，但和b选项一样。
所以看题要看选项

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

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

若邻接矩阵为

011

000

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
0 0 0
这个就不唯一
发表于 2022-08-25 13:50:15 回复(0)
zZZ-1头像 zZZ-1
求解析：怎么判断拓扑序列是否存在？
发表于 2022-07-01 18:46:58 回复(1)
questRush头像 questRush
B和D都对
发表于 2024-10-21 12:55:18 回复(0)
牛客76165061号头像 牛客76165061号
为什么不是D，主对角线以下又不包括对角线，如果有自环呢
发表于 2024-03-09 14:49:41 回复(0)
牛客131181223号头像 牛客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
从这图明显看出来:
  1. 要做3,必须先做2
  2. 要做2必须先做1
  3. 要做1,必须先做0
所以答案选A: 存在且唯一

发表于 2023-10-27 22:49:59 回复(0)
云云云一飞冲天头像 云云云一飞冲天
这题答案错了，应该选B，即存在但可能不唯一；
拓扑排序的充要条件是有向无环图；
从邻接矩阵的对角线一下元素都为零可以判断出，这个有向图只有顶点i到顶点j（i<j）可能有边，反之肯定没有边，必定是有向无环图，所以必然存在拓扑序列；
然后举个例子说明拓扑序列可能不唯一即可；
如：
0 1 1
0 0 0
0 0 0
这个就不唯一
发表于 2022-08-25 13:50:15 回复(0)
一枚蛋Oops头像 一枚蛋Oops
A
发表于 2019-11-21 13:33:07 回复(1)
提交观点

问题信息

图
上传者：城市里的养猫者
难度：
9条回答 3029浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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