题36

题36

题目

【2016 统考真题】若对 个顶点、 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是 ( ).
A.
B.
C.
D.

分析

拓扑排序，每次找到入度为0的点，删除这个点，同时删除这个点的出度，直到所有点都被删除。
邻接表是这样存的，每个点是链表头，自己指向那个点，或者说和哪个点相邻相连，就挂在链表后面
所以时间复杂度是

解

B
采用邻接表作为 AOV 网的存储结构进行拓扑排序,需要对 个顶点做进栈、出栈、输出各一次,当处理 条边时,需要检测这 个顶点的边链表结点,共需要的时间为 。
若采用邻接矩阵作为 AOV 网的存储结构进行拓扑排序,在处理 条边时需对每个顶点检测相应矩阵中的某一行,寻找与它相关联的边,以便对这些边的入度减 1,需要的时间代价为
【补充】有两种常用的拓扑排序算法: 基于 BFS 的算法和基于 DFS 的算法。
本题未指明采用哪种算法, 因此只需验证一种算法即可 (说明两种算法在对应条件下的时间复杂度相同)。
基于 BFS 的算法的思想: 首先找到所有入度为 0 的结点, 将它们加入一个队列, 并将它们作为拓扑序列的起始部分; 然后依次从队列中取出结点, 并删除它们与后继结点的所有边。若某个后继结点的入度变为 0 , 则将它也加入队列, 并将它加入拓扑序列, 重复这个过程。
基于 DFS 的算法的思想: 在 DFS 调用过程中设定一个时间标记, 当 DFS 调用结束时, 对各结点计时, 进而按结束时间从大到小排序, 可以得到一个拓扑序列。