图采用邻接矩阵和邻接链表表示时,深度优先遍历算法的时间复杂度有何不同？
发布网友
发布时间：2022-04-24 07:55
共3个回答
热心网友
时间：2023-10-09 01:35
1.采用邻接矩阵表示时，设邻接矩阵有n×n阶，矩阵包含n^2个元素。对每个顶点来说，搜索其所有邻接点需要搜索矩阵中对应的整个一行，因此，对整个图的遍历来说，需要搜索整个矩阵，算法的时间复杂度为O(n^2)。
2.采用邻接表表示时，若邻接表有n个结点和e条边，对每个顶点来说，搜索其所有邻接点需要搜索邻接表中对应的链表的各结点，算法的时间复杂度为O(n+e)。
扩展资料：
深度优先遍历算法的步骤：
（1）访问顶点V0；
（2）依次从V0的各个未被访问的邻接点出发深度遍历。
热心网友
时间：2023-10-09 01:36
邻接矩阵：矩阵包含n^2个元素，在算法中，共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O(n^2)
邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为
O（n+e）
顺便，对于广度优先算法的时间复杂度，也是这样来自：求助得到的回答
热心网友
时间：2023-10-09 01:36
