首页 > 试题广场 >

下列有关图的说法错误的是（）

[不定项选择题]

下列有关图的说法错误的是（）

在有向图中，出度为 0 的结点成为叶子结点

用邻接矩阵表示图，可以在 O(1) 时间复杂度内判断任意两个结点之间是否有边相连，并求得各结点的度

按深度优先遍历图和前序遍历树类似，得到的结果是唯一的

若有向图 G 中从结点 Vi 到结点 Vj 有一条路径,则在图 G 的结点的线性序列中结点 Vi 必在结点 Vj 之前的话,则称为一个拓扑序列

查看正确选项

Echo201811262032380

A. 图是更加广义的树，也有叶子节点。 C. DFS,BFS的结果均不同，要看规则，比如先左后右，还是先右后左。 D. 拓扑序列

发表于 2019-10-09 07:53:02 回复(0)

༄奥利奥࿐ེ

深度优先搜索（DFS）序列不唯一，他与算法、图的存储结构及出发点有关

发表于 2019-06-19 10:34:48 回复(0)

很白的月色

B错是因为求两节点间的度数至少也要扫描一行吧..，因此是O(n)

发表于 2022-03-02 18:08:52 回复(3)

牛客890903030号

D选项，有向图不知道是不是有环的，拓扑序就不知道谁前谁后了吧

发表于 2023-08-26 21:25:08 回复(0)

捞个offer

邻接矩阵：是找两个节点是否存在存在边比较快D[i][j],D[j][i]在O（1）就能找到。但是不能在O（1）时间内找到各个结点直接的度。需要遍历整个矩阵。B错。

图可以看成是树的延申，但图中没有明确的左孩子和右孩子的说法，因此无法确定这个遍历的顺序。C错。

发表于 2023-03-09 09:48:06 回复(0)

universal猿

D 节点vi到vj有路径，则图线性序列中vi到vj总是有序列，说明图中不存在环

发表于 2020-06-19 17:03:12 回复(0)

questRush

可以在 O(1) 时间复杂度内判断任意两个结点之间是否有边相连，并求得各结点的度 != 可以在 O(1)时间复杂度内求得各结点的度语文老师死得早就不要出题了好吗

发表于 2024-10-21 13:04:24 回复(0)

辉小歌

B，单独的邻接矩阵只可以判断俩点是否有边。度数没法用邻接矩阵记录查不了。 C，不唯一，可以想到的是dfs是不到底不回头，但是dfs开始选的路可能是不同的。

发表于 2022-07-13 08:16:20 回复(0)

学术废物

没看到还要求各点的度……

发表于 2022-03-16 21:53:51 回复(0)

AAS48

图是更加广义的树，也有叶子节点

发表于 2021-12-09 23:05:45 回复(0)

牛客609886776号

图的深度遍历结果不唯一。

发表于 2020-11-17 22:04:43 回复(0)

天尊墨宇

A. 图是更加广义的树，也有叶子节点。 C. DFS,BFS的结果均不同，要看规则，比如先左后右，还是先右后左。 D. 拓扑序列

综上选C

发表于 2020-07-12 10:11:14 回复(0)

牛客218196695号

DFS的出发点不同它的访问序就不同.

发表于 2020-04-23 21:29:31 回复(0)

逐梦者的脚步

在邻接表不确定或者没给出的情况下，深度优先和广度优先均有多种可能。

发表于 2019-05-27 09:43:04 回复(0)

提交观点

问题信息

算法工程师京东图 2019

上传者：小小

难度：

14条回答 288收藏 6787浏览

下列有关图的说法错误的是（）

问题信息

热门推荐

相关试题