最小生成树Prim算法（邻接矩阵和邻接表）

Prim算法是一种用于寻找加权无向连通图的最小生成树的算法。它的基本思想是，从一个顶点出发，每次将一个未被访问的且与当前已被访问的点集相连的权值最小的边加入生成树中，直到所有的顶点都被访问。

Prim算法有两种实现方式：邻接矩阵和邻接表。

邻接矩阵实现：

首先，我们需要用一个二维数组来表示图的邻接矩阵。其中，第i行第j列的元素表示顶点i和顶点j之间的边的权值。如果两个顶点之间没有边，则相应的元素为无穷大。我们还需要用一个一维数组来记录每个顶点是否已被访问，以及每个顶点的最小权值边。

算法流程如下：

1.初始化：将起始顶点加入已被访问的点集中，将该点的所有邻接边的权值存入最小权值数组中，将该点的最小权值设置为0。

2.重复以下步骤，直到所有顶点都被访问：

a.从未访问的点集中选择一个顶点u，使得u的最小权值最小。

b.将u加入已访问的点集中。

c.对于u的每个邻接顶点v，如果v未被访问且u到v的边的权值小于v的最小权值，则更新v的最小权值为u到v的边的权值。

邻接表实现：

与邻接矩阵相比，邻接表的实现方式更加节省空间。我们可以用一个数组来表示所有的顶点，每个顶点对应一个链表，存储该顶点与其他顶点之间的边及其权值。

算法流程如下：

1.初始化：将起始顶点加入已被访问的点集中，将该点的所有邻接边的权值存入最小堆中。

2.重复以下步骤，直到所有顶点都被访问：

a.从最小堆中取出一个权值最小的边。

b.如果该边的两个顶点都已被访问，则舍弃该边。

c.如果该边的一个顶点已被访问，则将另一个顶点加入已访问的点集中，并将该点的所有邻接边的权值存入最小堆中。

d.如果该边的两个顶点都未被访问，则将任意一个顶点加入已访问的点集中，并将该点的所有邻接边的权值存入最小堆中。