最小生成树-普利姆(Prim)算法及C语言/C++代码实现

1.最小生成树（又名：最小权重生成树）

概念：连接所有给定点（即从一个点可以到达任意点且连接路径总和最小的图称为最小生成树）。最小生成树属于树结构（树结构是图的一种特殊形式）或者线性结构，因为当n个点相连且路径之和最短时，那么连接它们的路径一定是n - 1 篇文章。

可以通过一个问题来理解最小生成树。有n个村庄，每个村庄之间的距离不同。村庄之间必须修建道路。每个村庄都必须与每个村庄相连。如何以最经济的方式修建道路（最短的修复时间）。

2。 普利姆算法简介

普利姆（Prim）算法寻找最小生成树，即在包含n个顶点的连通图中，只找到包含所有n个节点的（n-1）个连接。子图就是所谓的最小连通子图。

具体过程如下：

(1) 假设G=(V,E)为连通网络，T=(U,D)为最小生成树，V,U为顶点集，E , D 是边相交。

(2) 如果从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，并标记顶点v的visited[u]=1。

(3)如果集合U的顶点ui和集合V-U的顶点vj之间存在边，则找到这些边中权重最小的边，但不能形成环，将顶点vj添加到集合U中，并且add 将边 (ui, vj ) 添加到集合 D 中，标记为visited[vj]=1。

(4) 重复步骤②，直到U和V相等，即所有顶点都被标记为已访问。此时D中有n-1条边。

3。代码实现

不同的问题有不同的详细实现方法，所以此代码仅供参考