你好，请问用邻接表存储无向图，进行深度优先搜索的时间复杂度为什么

你好，请问用邻接表存储无向图，进行深度优先搜索的时间复杂度为什么不是O(n+2e),而是O(n+e)呢？... 你好，请问用邻接表存储无向图，进行深度优先搜索的时间复杂度为什么不是O(n+2e),而是O(n+e)呢？展开

 我来答

1个回答

#热议# 生活中有哪些实用的心理学知识？

姐姐是女孩子
2017-06-07 · TA获得超过537个赞

知道小有建树答主

回答量：932

采纳率：22%

帮助的人：112万

我也去答题访问个人页

关注

展开全部

设有n个点，e条边
邻接矩阵：矩阵包含n^2个元素，在算法中，共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O(n^2)
邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为
O（n+e）
顺便，对于广度优先算法的时间复杂度，也是这样

本回答被网友采纳

已赞过已踩过<

你对这个回答的评价是？
评论收起

推荐律师服务：若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询

你好，请问用邻接表存储无向图，进行深度优先搜索的时间复杂度为什么

其他类似问题

为你推荐：