如题所述
1.采用邻接矩阵表示时,设邻接矩阵有n×n阶,矩阵包含n^2个元素。对每个顶点来说,搜索其所有邻接点需要搜索矩阵中对应的整个一行,因此,对整个图的遍历来说,需要搜索整个矩阵,算法的时间复杂度为O(n^2)。
2.采用邻接表表示时,若邻接表有n个结点和e条边,对每个顶点来说,搜索其所有邻接点需要搜索邻接表中对应的链表的各结点,算法的时间复杂度为O(n+e)。
扩展资料:
深度优先遍历算法的步骤:
(1)访问顶点V0;
(2)依次从V0的各个未被访问的邻接点出发深度遍历。