图采用邻接矩阵和邻接链表表示时,深度优先遍历算法的时间复杂度有何不同？
答案:2 悬赏:0 手机版
解决时间 2021-03-25 06:54
- 提问者网友：爱了却不能说
- 2021-03-24 06:59
图采用邻接矩阵和邻接链表表示时,深度优先遍历算法的时间复杂度有何不同？
最佳答案
- 五星知识达人网友：你可爱的野爹
- 2021-03-24 07:45
设有n个点，e条边
邻接矩阵：矩阵包含n^2个元素，在算法中，共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O(n^2)
邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为
O（n+e）
顺便，对于广度优先算法的时间复杂度，也是这样来自：求助得到的回答
邻接矩阵：矩阵包含n^2个元素，在算法中，共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O(n^2)
邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为
O（n+e）
顺便，对于广度优先算法的时间复杂度，也是这样来自：求助得到的回答
全部回答
- 1楼网友：行路难
- 2021-03-24 08:24
用邻接矩阵时需要访问顶点的所有n的元素，DFS的时间为n平方，用邻接表时需访问所有点和点边节点为O（n+e）
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯