离散数学最小生成树例题
一个简单的离散数学的最小生成树例题如下：
给定一个带权无向连通图，顶点集合为{A, B, C, D, E, F, G, H}，边集合为{(A, B, 7), (A, D, 5), (B, C, 8), (B, D, 9), (B, E, 7), (C, E, 5), (D, E, 15), (D, F, 6), (E, F, 8), (E, G, 9), (F, G, 11), (F, H, 9), (G, H, 10)}。

要求使用Prim算法求解该图的最小生成树，并求出最小生成
树的权重。

首先，从任意一个顶点开始，假设选择顶点A作为起点，将
A加入最小生成树中。

接下来，利用Prim算法，选择与最小生成树中顶点相邻且权
重最小的边，且该边连接的顶点不在最小生成树中。

由题目可知，A与B边的权重最小，所以选择边(A, B, 7)。

将B加入最小生成树中。

再次选择与最小生成树中顶点相邻且权重最小的边，且该边连接的顶点不在最小生成树中。

此时，顶点C与顶点B相邻，
边的权重为8。

将C加入最小生成树中。

接着选取边(B, E, 7)，将E加入最小生成树中。

然后选取边(E, C, 5)，由于C已经在最小生成树中，故不作处
理。

接下来选取边(E, G, 9)，将G加入最小生成树中。

继续选取边(G, H, 10)，将H加入最小生成树中。

最后选取边(H, F, 9)，由于F已经在最小生成树中，故不作处理。

至此，所有的顶点都被加入了最小生成树中，最小生成树的权重为7+8+5+7+9+10+9=55。

所以，该图的最小生成树为{(A, B, 7), (B, E, 7), (C, E, 5), (E, G, 9), (G, H, 10), (H, F, 9)}，最小生成树的权重为55。