DFS和BFS的复杂度和其他习题

DFS算法是一一个递归算法，需要借助一个递归工作栈，故它的空间复杂度为O(N)。遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用结构。

邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O(N),此时，总的时间复杂度为O(N+E)。

邻接矩阵表示时，查找每个顶点的邻接点所需时间为O(N)，要查找整个矩阵，故总的时间度为O(N^2)。

BFS是一种借助队列来存储的过程，分层查找，优先考虑距离出发点近的点。无论是在邻接表还是邻接矩阵中存储，都需要借助一个辅助队列，N个顶点均需入队，最坏的情况下，空间复杂度为O(N)。

邻接表形式存储时，每个顶点均需搜索一次，时间复杂度T1=O(N)，从一个顶点开始搜索时，开始搜索，访问未被访问过的节点。最坏的情况下，每个顶点至少访问一次，每条边至少访问1次，这是因为在搜索的过程中，若某结点向下搜索时，其子结点都访问过了，这时候就会回退，故时间复 杂度为O(E)，算法总的时间复 度为O(N+E)。

邻接矩阵存储方式时，查找每个顶点的邻接点所需时间为O(N)，即该节点所在的该行该列。又有n个顶点，故算总的时间复杂O(N^2)。

全连通图的定点 n 和边数 m 满足：m = n(n-1)/2，那么边 m = 22 时, 图 G: n(n-1)/2 >= 22 解得：n >= 8 而且，当 n = 7 时，全连通图 G’ 的边数 m = 21 当我们把第 8 个定点专加上来，必然还要再在这个定点和上面7个定点相连，以属便构成第 22 边(8个顶点不足以构成22边非连通图) 加上第 9 个定点后，可以在 (8, 9) 之间构成第22边，或者，选择 8, 或 9 作为孤立点，构成非连通图 至少有 9 个顶点

详解来自牛客：这个网有三条关键路径： b、d、c、g b、d、e、h b、f、h 缩短工期的活动要涵盖三条路径。