在用邻接表表示图时,拓扑排序算法时间复杂度为()
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)。
列举一款你常用的移动APP,并分析他的最核心功能、满足的需求、超预期的功能以及竞争优势和发展趋势
某公园内有个奇怪的摊主小周,他只在星期一、星期二、星期三、星期五和星期六工作,而且他只出售4种商品:玩具汽车、充气气球、橡皮泥和遥控飞机。<
什么是 Cookie?它的作用是什么?
基于TCP协议建立连接和结束连接的过程
很基础的题,但还是要细心才能做对
拓扑排序结果不唯一,可以判断是否有环,针对有向图。时间复杂度为O(n+e),空间复杂度为O(n)。