用邻接表存储含n个顶点e条边的有向无环图G,对G进行拓扑排序,算法的时间复杂度为______。
【正确答案】:O(n+e)
【题目解析】:拓扑排序每次访问一个入度为0的顶点,图中如果没有回路,则需要扫描邻接表中的所有边结点,所以时间复杂度为O(n+e)。P165
用邻接表存储含n个顶点e条边的有向无环图G,对G进行拓扑排序,算法的时间复杂度为______。
- 2024-08-04 00:30:32
- 数据结构(02331)