c++c++普里姆算法构造最小生成树画图

普里姆算法（Prim's algorithm）是一种用来构造最小生成树的算法。

假设有一个带权重的无向连通图G，我们想要构造一个最小生成树。以下是使用普里姆算法构造最小生成树的步骤，并通过画图说明：

1. 首先，选择一个起始顶点，将其标记为已访问。

2. 从起始顶点开始，查找与已访问顶点相邻的未访问顶点，并找到连接这两个顶点的边的权重最小值。选择这条边，并将与未访问顶点相邻的顶点标记为已访问。

3. 重复第2步，直到所有顶点都被标记为已访问。此时，最小生成树构建完成。

让我们通过一个具体例子来说明：

假设有如下的无向连通图G：

    A --2-- B
   / \     / \
  1   3   5   4
 /     \ /     \
D--2--E--6--F--5--G

我们从顶点A开始构造最小生成树：

1. 选择顶点A作为起始顶点，并标记为已访问。

2. 查找与A相邻的未访问顶点，即B、D，选取权重最小的边AD。

3. 将顶点D标记为已访问。

4. 查找与已访问顶点（A和D）相邻的未访问顶点，即B、E。选取权重最小的边BE。

5. 将顶点E标记为已访问。

6. 查找与已访问顶点（A、D和E）相邻的未访问顶点，即B、F。选取权重最小的边AF。

7. 将顶点F标记为已访问。

8. 查找与已访问顶点（A、D、E和F）相邻的未访问顶点，即B、G。选取权重最小的边FG。

9. 将顶点G标记为已访问。

最终，我们得到的最小生成树如下图所示：

    A --- B
   /       \
  1         4
 /           \
D---2---E---5--F---G

这就是使用普里姆算法构造最小生成树的过程，并通过画图展示了最终的结果。