生成树、Prime、Kruskal

1、任何一个带权无向连通图的最小生成树——可能是不唯一的。

2、给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：14

3、给定有权无向图如下。关于其最小生成树，最小生成树不唯一，其总权重为23。

4、给出如下图所示的具有 7 个结点的网 G，采用Prim算法，从4号结点开始，给出该网的最小生成树。树结点收集顺序是4563201.

5、已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是：(b,f), (b,d), (a,e), (c,e), (b,e)

6、无向连通图的最小生成树有一个或多个。

7、若一个无向连通图没有权值相同的边，则该无向图的最小生成树唯一。

8、在求最小生成树时，Kruskal算法更适合于稀疏图。

9、给定下图，其最小生成树的总权重是30.

10、适合构造一个稠密图G的最小生成树Prime算法。

11、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为O(n+e)。

12、给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：23.

13、任何一个无向连通图的最小生成树有一颗或者是多颗。

14、在求最小生成树时，Prim算法更适合于稠密图。

15、用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是逆拓扑有序序列。

16、如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是连通图。

17、给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：V1,V5,V4,V7,V6,V3,V2

18、在图中自c点开始进行广度优先遍历算法可能得到的结果为：c,f,a,d,e,b。

19、给定一有向图的邻接表如下。若从v1开始利用此邻接表做广度优先搜索得到的顶点序列为：{v1, v3, v2, v4, v5}，则该邻接表中顺序填空的结果应为：v3, v2, v4。

20、给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：8.

21、用于求解最小生成树的是Prime算法。

22、克鲁斯卡尔（Kruskal）算法：

• 假设连通图G=(V,E)，其中V是顶点集，E是边集。初始时，最小生成树T=(V′,E′)，V′为图G中所有顶点的集合，E′为空集。
• 从E中选取权值最小的边，若将该边加入E′中不会形成回路，则将其加入E′；否则，舍弃该边。
• 重复上述步骤，直到E′中的边数为n−1或者所有边都已考察过为止，其中n是图G中顶点的个数。此时T=(V′,E′)就是图G的一棵最小生成树。

23、Prime算法 ：

• 从图中任意选择一个起始顶点v0​，将其加入到最小生成树的顶点集合U中。
• 不断从与U中顶点相邻的边中选择权值最小的边，将该边及其对应的另一个顶点加入到U中，直到所有顶点都被加入到U中。