Question

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

当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O(n^2),其中n为顶点数． 而当以邻接表作图的存储结构时，找邻接点所需时间为O(e),其中e为无向图中边的数或有向图中弧的数．　 由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n e). 请问上面这段话是什么意思？ 　　为什么用邻接矩阵表示时，查找每个顶点的邻接点所需时间为O(n^2)？ 　　而当以邻接表作图的存储结构时，找邻接点所需时间为O(e)？且深度优先搜索遍历图的时间复杂度为O(n e)？ 　　谢谢谢谢 　　

Answer 1

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

Answer 2

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