用邻接表存储含n个顶点e条边的有向无环图G，对G进行拓扑排序，算法的时间复杂度为______。
2024-08-04数据结构(02331)
用邻接表存储含n个顶点e条边的有向无环图G，对G进行拓扑排序，算法的时间复杂度为______。
【正确答案】：O（n+e）
【题目解析】：拓扑排序每次访问一个入度为0的顶点，图中如果没有回路，则需要扫描邻接表中的所有边结点，所以时间复杂度为O（n+e）。P165
【正确答案】：O（n+e）
【题目解析】：拓扑排序每次访问一个入度为0的顶点，图中如果没有回路，则需要扫描邻接表中的所有边结点，所以时间复杂度为O（n+e）。P165
扫描二维码免费使用微信小程序搜题/刷题/查看解析。
版权声明：本文由翰林刷题小程序授权发布，如需转载请注明出处。