题14
题目
Q:假设有 个顶点、 条边的有向图用邻接表表示，则删除与某个顶点 相关的所有边的时间复杂度为 ( ) .
A.
B.
C.
D.
分析
A:邻接表要把整个图遍历一遍，需要走 个顶点， 条边，也就是走两遍，所以时间复杂度为 。
解
C
与顶点 相关的边包括出边和入边,对于出边,只需遍历 的顶点表结点和其指向的边表;
对于入边,则需遍历整个边表。
先删除出边: 删除 的顶点表结点的单链表,出边数最多为 ,时间复杂度为 ;
再删除入边: 扫描整个边表 (即扫描剩余全部顶点表结点及其指向的边表),删除所有的顶点 的入边,时间复杂度为 。所以总时间复杂度为 。