假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点v相关的所有弧的

admin2022-08-02 45

问题假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点v相关的所有弧的时间复杂度是()。A.O(n)B.O(e)C.O(n+e)D.O(n×e)

选项 A.O(n)
B.O(e)
C.O(n+e)
D.O(n×e)

答案 C

解析由有向图的邻接表存储结构可知，每个顶点v链接的顶点只包含从v发出的弧所指向的顶点，不包含指向v的弧所对应的尾结点。又因为邻接表的结点数是边数与顶点数的总和，所以要删除与某个顶点相关的所有弧时间复杂度为O(n+e)。

转载请注明原文地址:https://tihaiku.com/gongwuyuan/2555003.html

计算机电网

相关试题推荐

随机试题

最新回复(0)