---

1）

Prim 算法思想：

• 从图中任意一个顶点开始，把它加入生成树集合。

• 每次从生成树集合中选出与树中顶点相连且权值最小的边，将该边和新顶点加入生成树。

• 重复直到所有顶点都加入生成树。

• 本质是逐步扩展生成树。

Kruskal 算法思想：

• 将所有边按权值从小到大排序。

• 从最小边开始，依次加入生成树，但要避免形成环。

• 使用并查集（Union-Find）判断是否形成环。

• 重复直到生成树有 n-1 条边。

• 本质是逐步选择最小边构建生成树。

2）

证明思路：

1. 假设存在两棵不同的最小生成树 MST1 和 MST2。

2. 在 MST1 中存在一条边 e1 不在 MST2 中。

3. 在 MST2 中加入 e1，会形成环。环中一定存在另一条边 e2 ∈ MST2 且 e2 ∉ MST1。

4. 因为边权唯一，weight(e1) ≠ weight(e2)。

   • 若 weight(e1) < weight(e2)，替换 e2 会得到更小权值的生成树 → 与 MST2 最小矛盾

   • 若 weight(e1) > weight(e2)，替换 e1 会得到更小权值的生成树 → 与 MST1 最小矛盾

5. 两种情况都矛盾，所以假设不成立 → MST 唯一。

所以，当边权值各不相同时，最小生成树唯一。

3）

1. 初始生成树：{A}

   • 与 A 相连边：AB(6), AC(1), AD(5)

   • 选择最小边 AC(1)

   • 生成树更新：{A,C}，边集 {AC(1)}

2. 生成树：{A,C}

   • 与树外顶点相连边：AB(6), AD(5), CB(5), CD(5), CE(6), CF(4)

   • 选择最小边 CF(4)

   • 生成树更新：{A,C,F...