题目内容
(请给出正确答案)
[主观题]
有向图有n个顶点e条弧,采用邻接表存储,则计算某顶点度的算法需要访问n+e个单链表的表结点。
答案
(6)O(n+e) (7)O(n 2 ) (6)O(n+e) (7)O(n 2 ) 解析:邻接表:对有n个顶点和e条弧的有向图而言,在拓扑排序中,若有向图无环,则每个顶点进出队列各一次,共执行e次,搜索算法时间复杂度是由n和e共同决定的,所以总的时间复杂度为O(n+e)。 当用邻接矩阵:对于每个顶点,查找相邻边的时间复杂度是O(n),一共有n个顶点,所以总的时间复杂度是O(n 2 )。
如搜索结果不匹配,请 联系老师 获取答案