共计 2293 个字符，预计需要花费 6 分钟才能阅读完成。
下面 4 张有向图中，哪个不属于强连通图。（B）
首先明确何为强连通图：对一个有向图，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。
判定方法：任取有向图 G 的某结点 S，从 S 开始进行深度优先搜索，若可以遍历 G 的所有结点；再将 G 的所有边反向，再次从 S 开始进行深度优先搜索，如果再次能够遍历 G 的所有结点，则 G 是强连通图，两次搜索有一次无法遍历所有结点，则 G 不是强连通图。此外，上述搜索可以换成广度优先搜索等其他方案。
某个无向图共有 16 条边，每个顶点的度均为 2，则该无向图的顶点数为（16）
每条边有两个顶点，所以总度数为 16*2=32；又因为每个点度数为 2，所以一共 16 条边
若某无向图一共有 16 条边，并且有 3 个度为 4 的顶点，4 个度为 3 的顶点，其余顶点的度均小于 3，则该无向图至少有多少个顶点？至多有多少个节点
每条边有两个顶点，16*2=32，所以总度数为 32；
32-34-43=8
剩余节点度均小于 3，则最大为 2
所以至少的就是剩余节度点均为 2，即 8 /2=4，则得到 3 +4+4=11
最大的就是剩余节度点均为 1，是 3 +4+8=15
求下图中顶点 0 到 5 的最短路径是（012435）
我们使用 Dijkstra 算法来求两点间最短路径：
第 1 步：所有 Wi 初始化为无穷大∞；
第 2 步：设 0 已访问；更新与 0 直接相连的所有结点的 W；并将这些结点加入“待访问结点列表”。w1=1，w2=4;
第 3 步：找出 中 W 最小的结点，设其“已访问”；即 w1 已访问。考察与它直接相连的未访问结点 (若有与已访问节点相连的不再考察)，累加并更新它们的 W(若比所保存的 W 小才更新)，并将它们加入“待访问结点列表”。w2=3,w3=8,w4=6
第 3 步（重复此步）：找出待访问中 W 最小的结点，设其“已访问”；w2.
考察与它直接相连的、未访问结点(若有与已访问节点相连的不再考察)，累加并更新它们的 W(若比所保存的 W 小才更新)，并将它们加入“待访问结点列表”。w4=4
下列关于 AOE 网的叙述中, 不正确的是(B)
- 关键活动不按期完成就会影响整个工程的完成时间
- 任何一个关键活动提前完成, 那么整个工程将会提前完成
- 所有的关键活动提前完成, 那么整个工程将会提前完成
- 某些关键活动若提前完成, 那么整个工程将会提前完成
首先要知道何为关键活动和关键路径，关键路径是图中的最长路径，关键路径长度代表整个工期的最短完成时间；关键活动则组成了关键路径
关键活动延期完成，必将导致关键路径长度增加，即整个工期的最短完成时间增加，因此 A 正确。
关键路径并不唯一，当有多条关键路径存在时，其中一条关键路径上的关键活动时间缩短，只能导致本条关键路径变成非关键路径，而无法缩短整个工期，因为其他关键路径没有变化，因此 B 项不正确。
对于 A，B 两项要搞懂的是，当关键路径不唯一时，任何一条关键路径上的关键活动变长，都会使这条关键路径变成更长的关键路径，并且导致其他关键路径变成非关键路径，因此整个工期延长。所以某些关键活动缩短则不一定缩短整个工期。理解了 A,B 两项，C,D 就很容易理解了
用 DFS 遍历一个无环有向图，并在 DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是(逆拓扑有序)
DFS 是一个递归算法, 在遍历的过程中, 先访问的点被压入栈底。
拓扑有序是指如果点 U 到点 V 有一条弧, 则在拓扑序列中 U 一定在 V 之前.
深度优先算法搜索路径恰恰是一条弧, 栈的输出是从最后一个被访问点开始输出, 最后一个输出的点是第一个被访问的点. 所以是逆的拓扑有序序列
下面所示的有向图，其拓扑排序的结果序列是（）。
- A.125634
- B.516234
- C.123456
- D. 521643
第一种做法，排除法：按照拓扑排序的定义，若有向无环图中存在一条从 i 到 j 的边，则拓扑排序中 i 一定在 j 的前面。我们就看有没有 j 在 i 前边的
第二种做法，每次选取极大顶点（入度为 0 的顶点），并把它跟它的出度一起从图中删掉
任一个有向无环图的拓扑序列的数量有（一个或多个）。
有向无环图的拓扑排序可以看成图的层序遍历，每一层的顶点可以有不同的顺序，这就造成拓扑排序序列不唯一
一个 n 个顶点的连通无向图, 其边的个数至少为(N-1)
完全图是每对顶点之间都恰连有一条边的简单图，N 个端点的完全图有 n(n−1)/2 条边。
而一个 n 个顶点的连通无向图, 其边的个数至少为 n – 1，即最小生成树的边数
在用邻接表表示图时，拓扑排序算法时间复杂度为(O(n+e) )。
对有 n 个顶点和 e 条弧的有向图而言，建立求各顶点的入度的时间复杂度为 O(e)；建零入度顶点栈的时间复杂度为 O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈、出一次栈，入度减 1 的操作在 while 语句中总共执行 e 次，所以总的时间复杂度为 O(n+e)。拓扑排序初始参数只有邻接表，所以第一步建立入度数组，因为每 1 入度对应一条弧，总共 e 条弧，建立入度数组的复杂度为 O(e)。每个节点输出一次，n 个节点遍历一次，时间复杂度为 O(n)。（使用零入度节点栈的原因是，如果不把零入度节点入栈，每次输出时都要遍历节点。建立此栈，只需遍历一次。）然后节点入度减 1 的操作，也是一条弧对应一次，e 条弧总共 O(e)。以上总计 O(n+2e)即 O(n+e)。即对每条弧要建立入度数组操作和删除操作，每个顶点要遍历一次并删除。故时间复杂度为 O(n+e)
