-
By: admin
好的，我们将使用普里姆（Prim）算法，以顶点 a 为起点，来找出这个连通图的最小生成树（MST）。
普里姆算法简介
普里姆算法是一种贪心算法，用于在加权连通图中寻找最小生成树。其基本思想是：
初始化：选择一个起始顶点，并将其放入一个集合 U 中，该集合表示已经包含在最小生成树中的顶点。
循环：重复以下步骤，直到所有顶点都进入集合 U 中。
在所有连接集合 U 内的顶点与集合 U 外的顶点的边中，找到一条权值最小的边。
将这条权值最小的边加入最小生成树，并将该边所连接的 U 外的顶点加入集合 U。
计算过程
给定的图信息：
顶点(Vertices): {a, b, c, d, e, f, g}
边(Edges)和权重(Weights):
ad(9), ab(2), af(5), bf(8), fg(1), bg(4), cg(6), bc(7), ec(10), be(3), bd(1), de(2)
以 a 为起点，逐步构建最小生成树：
初始状态:
已选顶点集合 U = {a}
最小生成树边集合 T = {}
总权重 = 0
第 1 步:
从集合 U = {a} 出发，寻找连接到集合外顶点的权值最小的边。
候选边：(a, b) 权重 2，(a, f) 权重 5，(a, d) 权重 9。
选择 (a, b)，因为它的权重最小。
操作:
将顶点 b 加入 U。现在 U = {a, b}。
将边 (a, b) 加入 T。
总权重 = 2。
第 2 步:
从集合 U = {a, b} 出发，寻找连接到集合外顶点的权值最小的边。
候选边 (忽略已连接到U内顶点的边):
从 a: (a, f) 权重 5, (a, d) 权重 9
从 b: (b, d) 权重 1, (b, e) 权重 3, (b, g) 权重 4, (b, c) 权重 7, (b, f) 权重 8
在所有候选边中，(b, d) 的权重最小。
操作:
将顶点 d 加入 U。现在 U = {a, b, d}。
将边 (b, d) 加入 T。
总权重 = 2 + 1 = 3。
第 3 步:
从集合 U = {a, b, d} 出发，寻找连接到集合外顶点的权值最小的边。
候选边:
从 a: (a, f) 权重 5
从 b: (b, e) 权重 3, (b, g) 权重 4, (b, c) 权重 7, (b, f) 权重 8
从 d: (d, e) 权重 2
在所有候选边中，(d, e) 的权重最小。
操作:
将顶点 e 加入 U。现在 U = {a, b, d, e}。
将边 (d, e) 加入 T。
总权重 = 3 + 2 = 5。
第 4 步:
从集合 U = {a, b, d, e} 出发，寻找连接到集合外顶点的权值最小的边。
候选边:
从 a: (a, f) 权重 5
从 b: (b, g) 权重 4, (b, c) 权重 7, (b, f) 权重 8
从 d: (无新的边)
从 e: (e, c) 权重 10
在所有候选边中，(b, g) 的权重最小。
操作:
将顶点 g 加入 U。现在 U = {a, b, d, e, g}。
将边 (b, g) 加入 T。
总权重 = 5 + 4 = 9。
第 5 步:
从集合 U = {a, b, d, e, g} 出发，寻找连接到集合外顶点的权值最小的边。
候选边:
从 a: (a, f) 权重 5
从 b: (b, c) 权重 7, (b, f) 权重 8
从 e: (e, c) 权重 10
从 g: (g, f) 权重 1, (g, c) 权重 6
在所有候选边中，(g, f) 的权重最小。
操作:
将顶点 f 加入 U。现在 U = {a, b, d, e, g, f}。
将边 (g, f) 加入 T。
总权重 = 9 + 1 = 10。
第 6 步:
从集合 U = {a, b, d, e, g, f} 出发，寻找连接到集合外顶点的权值最小的边。此时只剩下顶点 c 不在集合中。
候选边:
从 b: (b, c) 权重 7
从 e: (e, c) 权重 10
从 g: (g, c) 权重 6
在所有候选边中，(g, c) 的权重最小。
操作:
将顶点 c 加入 U。现在 U = {a, b, c, d, e, f, g}。
将边 (g, c) 加入 T。
总权重 = 10 + 6 = 16。
算法结束:
所有顶点都已包含在集合 U 中，最小生成树构建完成。
最终结果
该连通图的最小生成树包含以下几条边：
a — b (权重 2)
b — d (权重 1)
d — e (权重 2)
b — g (权重 4)
g — f (权重 1)
g — c (权重 6)
最小生成树的总权重为：16。
INF (无穷大) = 32767
--- 处理图 1 (顶点 A-G) ---
===================================Prim 算法结果 (从顶点 A 开始):----------------------------------- 当前 V-U 集合中的候选边 (lowcost > 0 且 < INF): * 边 (B, A)，权重: 2 * 边 (D, A)，权重: 9 * 边 (F, A)，权重: 5
--- 步骤 1.a: 查找 V-U 中 lowcost 最小的顶点 (min_cost 初始为 INF) ------ 查找完成：选取顶点 B，最小权重: 2 ------ 步骤 1.b: 更新 lowcost 和 closest (新加入顶点 B) --- * 检查顶点 V-U 中的 C：新边 (B,C) 权值 7 < 旧边 (A,C) 权值 INF，**更新** lowcost[C]=7，closest[C]=B。 * 检查顶点 V-U 中的 D：新边 (B,D) 权值 1 < 旧边 (A,D) 权值 9，**更新** lowcost[D]=1，closest[D]=B。 * 检查顶点 V-U 中的 E：新边 (B,E) 权值 3 < 旧边 (A,E) 权值 INF，**更新** lowcost[E]=3，closest[E]=B。 * 检查顶点 V-U 中的 F：新边 (B,F) 权值 8 >= 旧边 (A,F) 权值 5，**不更新**。 * 检查顶点 V-U 中的 G：新边 (B,G) 权值 4 < 旧边 (A,G) 权值 INF，**更新** lowcost[G]=4，closest[G]=B。--------------------------------------------------------- 当前 V-U 集合中的候选边 (lowcost > 0 且 < INF): * 边 (C, B)，权重: 7 * 边 (D, B)，权重: 1 * 边 (E, B)，权重: 3 * 边 (F, A)，权重: 5 * 边 (G, B)，权重: 4
--- 步骤 2.a: 查找 V-U 中 lowcost 最小的顶点 (min_cost 初始为 INF) ------ 查找完成：选取顶点 D，最小权重: 1 ------ 步骤 2.b: 更新 lowcost 和 closest (新加入顶点 D) --- * 检查顶点 V-U 中的 C：新边 (D,C) 权值 INF >= 旧边 (B,C) 权值 7，**不更新**。 * 检查顶点 V-U 中的 E：新边 (D,E) 权值 2 < 旧边 (B,E) 权值 3，**更新** lowcost[E]=2，closest[E]=D。 * 检查顶点 V-U 中的 F：新边 (D,F) 权值 INF >= 旧边 (A,F) 权值 5，**不更新**。 * 检查顶点 V-U 中的 G：新边 (D,G) 权值 INF >= 旧边 (B,G) 权值 4，**不更新**。--------------------------------------------------------- 当前 V-U 集合中的候选边 (lowcost > 0 且 < INF): * 边 (C, B)，权重: 7 * 边 (E, D)，权重: 2 * 边 (F, A)，权重: 5 * 边 (G, B)，权重: 4
--- 步骤 3.a: 查找 V-U 中 lowcost 最小的顶点 (min_cost 初始为 INF) ------ 查找完成：选取顶点 E，最小权重: 2 ------ 步骤 3.b: 更新 lowcost 和 closest (新加入顶点 E) --- * 检查顶点 V-U 中的 C：新边 (E,C) 权值 10 >= 旧边 (B,C) 权值 7，**不更新**。 * 检查顶点 V-U 中的 F：新边 (E,F) 权值 INF >= 旧边 (A,F) 权值 5，**不更新**。 * 检查顶点 V-U 中的 G：新边 (E,G) 权值 INF >= 旧边 (B,G) 权值 4，**不更新**。--------------------------------------------------------- 当前 V-U 集合中的候选边 (lowcost > 0 且 < INF): * 边 (C, B)，权重: 7 * 边 (F, A)，权重: 5 * 边 (G, B)，权重: 4
--- 步骤 4.a: 查找 V-U 中 lowcost 最小的顶点 (min_cost 初始为 INF) ------ 查找完成：选取顶点 G，最小权重: 4 ------ 步骤 4.b: 更新 lowcost 和 closest (新加入顶点 G) --- * 检查顶点 V-U 中的 C：新边 (G,C) 权值 6 < 旧边 (B,C) 权值 7，**更新** lowcost[C]=6，closest[C]=G。 * 检查顶点 V-U 中的 F：新边 (G,F) 权值 1 < 旧边 (A,F) 权值 5，**更新** lowcost[F]=1，closest[F]=G。--------------------------------------------------------- 当前 V-U 集合中的候选边 (lowcost > 0 且 < INF): * 边 (C, G)，权重: 6 * 边 (F, G)，权重: 1
--- 步骤 5.a: 查找 V-U 中 lowcost 最小的顶点 (min_cost 初始为 INF) ------ 查找完成：选取顶点 F，最小权重: 1 ------ 步骤 5.b: 更新 lowcost 和 closest (新加入顶点 F) --- * 检查顶点 V-U 中的 C：新边 (F,C) 权值 INF >= 旧边 (G,C) 权值 6，**不更新**。--------------------------------------------------------- 当前 V-U 集合中的候选边 (lowcost > 0 且 < INF): * 边 (C, G)，权重: 6
--- 步骤 6.a: 查找 V-U 中 lowcost 最小的顶点 (min_cost 初始为 INF) ------ 查找完成：选取顶点 C，最小权重: 6 ------ 步骤 6.b: 更新 lowcost 和 closest (新加入顶点 C) ------------------------------------------------------------
-----------------------------------最小生成树的总权重: 16===================================