用邻接表存储含n个顶点e条边的有向无环图G,对G进行拓扑排序,算法的时间复杂度为______。

作者:高老师 浏览 1

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

📱 扫码体验刷题小程序

微信小程序二维码

扫一扫使用我们的微信小程序

热门题目

已复制到剪贴板