一个含有n个顶点e条边的有向图用邻接表表示,删除与某个顶点相关的所有弧的时间复杂度怎么计算?

2025-05-15 17:26:37
推荐回答(1个)
回答1:

删除与某个顶点V欧相关的所有边的过程:先删除下标为V的顶点表节点的单链表,出边数最多为n-1,对应时间复杂度为O(n),再扫描所以边表的结点,删除所有的顶点V的入边,对应的时间复杂度为O(e)。故总的时间复杂度为O(n+e)。