图的深度优先搜索的时间复杂度

2025-02-28 07:51:27

推荐回答（2个）

回答1：

因为在邻接矩阵上遍历，一般至少需要将矩阵中元素一半给过一下，由于矩阵元素个数为n^2，因此时间复杂度就是O(n^2)
至于在邻接表上遍历时，过程与这个类似，但是邻接表中只是存储了边结点(e条边，无向图也只是2e个结点)，加上表头结点为n（也就是顶点个数），因此时间复杂度为O(n+e)
另外，在邻接表中判断某个顶点是否关联，最坏时可能需要将链表中所有结点都遍历完（尤其是有向图中），此时时间复杂度自然就是O(e)了

回答2：

邻接矩阵表示时，矩阵中元素的数目是n^2。查找每个顶点的邻接点需要访问矩阵中的所有元素。
邻接表作图的存储结构时，用着色法标记图上的点，图初始化所需时间为O(n)，每个顶点执行一次DFSTtraverse函数，一个顶点执行DFSTtraverse所需时间与和该顶点相邻的顶点数成正比，所有顶点执行DFSTtraverse函数所需时间的和与e成正比。