图习题课

有 8 个结点的无向连通图最少有（7）条边

无向连通图边最少的情况是生成树。n 个顶点有 n - 1 条边的无向图叫做生成树。权值最小的生成树是最小生成树。

用邻接表表示图进行深度优先遍历时，通常采用栈来实现算法，广度优先遍历使用队列。

深度优先遍历：类似于树的前序遍历。从图中的某个顶点 v 出发，访问此顶点，然后从 v 的未被访问到的邻接点进行遍历，直到图中所有和 v 有路径相通的顶点都被访问到
注：优先访问外层节点，访问到无新顶点时，会进行回退，访问未被访问过的分支顶点。
广度优先遍历：类似于树的层序遍历。从图中的某个顶点 w 出发，让顶点 w 入队，然后顶点 w 再出队，并让所有和顶点 w 相连的顶点入队，然后再出队一个顶点 t，并让所有和 t 相连但未被访问过的顶点入队……由此循环，指定图中所有元素都出队。

连通分量指的是有向图中的极大连通子图(错)

有向图中称为强连通分量。连通图和连通分量都是针对无向图

对于含有 n 个顶点 e 条边的连通图，利用 prim 算法求最小生成数的时间复杂度为（O(n²)）

首先，以一个结点作为最小生成树的初始结点，然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。（加入之后如果产生回路了就要跳过这条边，选择下一个结点。）当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树。

首先，初始化部分所需时间为 Ο(|V|+|E|)。
其次，在 |V|- 1 次循环过程中，一方面要遍历各个顶点的邻接边，一共需要 Ο(|E|)的时间；另一方面在每次循环中查找权重最轻的边需要对所有顶点遍历一遍，每次循环需时 Ο(|V|)。
因此算法的时间复杂度 T(n) =Ο(|V|+|E|) +Ο(|E|) + (|V|-1)Ο(|V|) =Ο(|V|^2+|E|) =Ο(|V|^2)。
边数较多可以用 Prim，因为它是每次加一个顶点，对边数多的适用。

任何一个无向连通图（有一棵或多棵）最小生成树。

无向连通图，从每一个顶点出发都会得到一棵对应的最小生成树，所以可以有很多棵，但是只有一个顶点时，就只能有一棵。

拓扑排序算法把一个无向图中的顶点排成一个有序序列。（错）

有向无环图才能进行拓扑排序。

求最短路径的 DIJKSTRA 算法的时间复杂度为 (O(n²)  )

最短路径的迪杰斯特拉算法其实和最小生成树的普里姆算法相类似，原理是一样的，故时间复杂度为 o(n^2).

一个活动的最早开始时间同该活动弧尾顶点的最早开始时间相同，一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的和。

首先，做这题要注意几点概念：
1）在 AOE 网络中，顶点表示事件，弧表示活动
2）如果顶点 A ->B 有弧，如果让弧表示为 L，则 A 为 L 的弧尾，B 为 L 的弧头，即有箭头的那一端叫头。

求关键路径是以拓扑排序为基础的。

(1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2). 利用 Dijkstra 求每一对不同顶点之间的最短路径的算法时间是 O(n3)；（图用邻接矩阵表示）(3). Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面正确的是（2）。

(1)迪杰斯特拉（Dijkstra）最短路径算法中将所有的顶点分为两部分：已经确定的最短路程的顶点集合 P 和不能确定的最短路径的顶点集合 Q，每一次遍历都能最少确定一个顶点，也就是说每一次遍历至少有一个顶点进入集合 P。归入 P 集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与 P 内某点（记为 a）以负边相连的点（记为 b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于 a 原先确定的最短路径长度, 而此时 a 在 Dijkstra 算法下是无法更新的，由此便可能得不到正确的结果.。(2)求的是一对顶点，时间复杂度跟 Floyd 算法一样都是 O(n^3)，如果求得是一个顶点到其他顶点的最短路径，时间复杂度才为 O(n^2)。