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

2025-03-06 22:13:47
推荐回答(1个)
回答1:

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