下面关于图的说法中，正确的有：

[不定项选择题]

下面关于图的说法中，正确的有：

可以使用邻接表或邻接矩阵来存储图；

对有n 个顶点、 e 条边且使用邻接表存储的有向图进行广度优先遍历的时间复杂度是O(n+e)；

```
没有回路的连通图也是树；
```

一个确定的有向无环图有且只有一种拓扑排序；

查看正确选项

pein531

邻接表形式存储时，每个顶点均需搜索一次，每次结点被入队一次，出队一次，所以时间复杂度是 O(V)，但是遍历某个顶点所有邻接点的复杂度是 O(e_i), e_i为第 i 条链表的弧的条数，也就是邻接点个数，所以查找所有邻接点的复杂度为 O(e₁ + e₂ + ... + e_n) = O(E), 加上对每个结点进行入队出队的复杂度 O(V), 所以总的时间复杂度为O(E + V)。

邻接矩阵存储方式时，查找每个顶点的邻接点所需时间为O(V)，即该节点所在的该行的所有列。又因为有n个顶点，查找所有邻接点的时间复杂度为O(V²)，加上对每个结点进行入队出队的复杂度 O(V), 所以总的时间复杂度为O(V²+ V)。省略低阶复杂度，最终复杂度为 O(V²)。

发表于 2021-07-13 11:19:59 回复(0)