在用邻接表表示图时,拓扑排序算法时间复杂度为()
A.O(n)
B.O(n*n*n)
C.O(n*n)
D.O(n+e)
正确答案是 D
若为避免重复检测入度为零的顶点,使用栈来保存所有入度为零的顶点。对有n个顶点和e条弧的有向图而言,建立求各顶点的入度的时间复杂度为O(e);建零入度顶点栈的时间复杂度为O(n);在拓扑排序过程中,若有向图无环,则每个顶点进一次栈,出一次栈,入度减一的操作在while循环中总共执行e次,所以总的时间复杂度为O(n+e)。
很基础的题,但还是要细心才能做对
拓扑排序结果不唯一,可以判断是否有环,针对有向图。时间复杂度为O(n+e),空间复杂度为O(n)。
使用js实现数组的快速排序
请实现KMP算法?
请你谈谈Cookie的弊端
怎么理解产品经理与技术研发之间的关系?
很基础的题,但还是要细心才能做对
拓扑排序结果不唯一,可以判断是否有环,针对有向图。时间复杂度为O(n+e),空间复杂度为O(n)。