对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度是()。
O(n)
O(e)
O(n+e)
O(n*e)
广度优先遍历需要借助队列实现。邻接表的结构包括:顶点表;边表(有向图为出边表)。当采用邻接表存储方式时,在对图进行广度优先遍历时每个顶点均需入队一次(顶点表遍历),故时间复杂度为O(n),在搜索所有顶点的邻接点的过程中,每条边至少访问一次(出边表遍历),故时间复杂度为O(e),算法总的时间复杂度为O(n+e)。
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
广度优先遍历需要借助队列实现。邻接表的结构包括:顶点表;边表(有向图为出边表)。当采用邻接表存储方式时,在对图进行广度优先遍历时每个顶点均需入队一次(顶点表遍历),故时间复杂度为O(n),在搜索所有顶点的邻接点的过程中,每条边至少访问一次(出边表遍历),故时间复杂度为O(e),算法总的时间复杂度为O(n+e)。