最小生成树是地图结构中简化地图的算法。 也就是说，删除某些边可以简化图并形成树结构，但必须保证图中的任意点相连。 的最小生成树必须与从顶点遍历时通过边的权重最小。 (如果有n个节点，则最小生成树的边数必须为n-1。)
例如：
成为最小生成树后：
有两种方法处理最小生成树。
1 .克鲁斯卡尔算法(kruskal ) :
该算法首先取出所有的边，按其权重从小到大的顺序排列，然后从最小的边开始恢复图，即在该边上连接其顶点。 从权重最小的边开始依次连接，对每个连接判断此次连接是否形成一个循环，如果是，则无需撤消更改，在撤消的边数达到n-1时完成最小生成树。
恢复步骤：
形成循环后，不会恢复边。
C代码参考代码(用于并列。 这是我对分类的理解) :
# include iostream # includealgorithmtypedefstruct//定义边缘的结构{ int value； 输入节点1、节点2； }edge； #define max_size 20int parent[20]； //安装节点的根using namespace std； intrule(edgea，edge b )//按权重对边进行排序时，选择{ return a.valueb.value； //升序排序) }intfind_root(intv )//查找根节点的函数(if ) parent[v]==-1 ) return v； else { parent [ v ]=find _ root (parent [ v ]； //压缩查找父节点的路径return parent[v]； }intis_cycle(intV1，int v2 ) /判断是否为循环(intV1_root=find_root ) V1 )； intV2_root=find_root(V2； if(V1_root==V2_root ) return 1；//两个节点的路由相同，连接两个节点时循环else { parent[v1_root]=v2_root； //连接，现在最好根据情况选择将v1或v2的根作为公共根return 0)的}voidkruskal(edgea (，edge b[] )、int n、int m ) { sort(a ) } for(intI=0，j=0； im； I ) if (！ is_cycle(a[I].node1，a[i].node2) ) /未形成循环) { b[j].node1=a[i].node1； b[j].node2=a[i].node2； b[j].value=a[i].value； j； //还原的边数if(j==n-1 ) break； } }}int main () (for ) intI=0； i20； I//初始化节点的父亲{ parent[i]=-1； (} int n，m； cinnm； //节点数n和边数m edge arr[m]； for(intI=0； im； I//初始化映射{ cinarr [ I ].node1arr [ I ].node2arr [ I ].value； } edge mst[n]； //用于放入最小生成树kruskal(ARR，mst，n，m )； coutendl； for(intI=0； 合1； I ) cout MST [ I ].node1' ' MST [ I ].node2' ' MST [ I ].value endl； } return 0； }执行结果：
2 .棱镜算法(Prim ) :
普里算法从某个端点出发，形成被选择的节点集合、未被选择的节点集合这2个集合。 找到从选定集到未选定集的最小权重边，使连接端点成为选定集。 重复此操作，直到所有节点在选定集合中完成操作。
现在让我谈谈我的想法：
在代码实现过程中，必须选择端点，然后将其更新为未选定节点集合的值。 这意味着，未从选定节点集合中选择的节点只有一个值。
步骤如下。
)从一个端点出发，使该端点成为选定节点(可以在数组中标记哪个是选定节点)。
)2)更新从选定端点到相邻节点的权重，当小于以前保存的值时更新(到相邻节点的权重的最初初始值为无限大)。
*例：初始值dis[1]=…=dis[6]=inf，inf无限大，只要保证大于所有权值即可。 选择v1时，可以看到到v2、v3、v4的权重小于inf，因此更新dis[2]=6，dis[3
]=1,dis[4]=5.*(3)找dis数组中最小值的下标，把改下标划为已选集合，更新dis数组；
例：v1更新完dis后，找到最小值为dis[3],把v3划为已选节点，通过v3，索引未选节点，更新到未选节点的距离，索引v2时：5<6,故dis[2]=5;索引v4时：5<5为假，故不必更新dis[4];索引v5时：6<inf,故dis[5]=6；索引v6时：4<inf,故dis[6]=4；更新完成后找到dis中最小权值的下标，把它划为已选节点，更新dis…重复操作，直到所有节点为已选节点
（4）重复（2）、（3）操作，直到所有的节点都为已选节点时结束。 //数组储存未选集合，每次选到未选集合的最短距离都要遍历数组一遍，有瑕疵#include<iostream>#include<vector>//使用向量容器，装相邻节点using namespace std;#define max_size 20#define inf 10000 //表示无穷大typedef struct{ int parent; int node;//节点序号 int value;//从已选节点到该节点的距离（权值） int flag;//该节点是否被选，1 已选，0 未选}node;typedef struct{ int node1; int node2; int value;}edge;vector<int> neighbor[max_size];//装相邻节点vector<int> value[max_size];//装到相邻节点的权值int j=0;//用于mst数组下标void Prim(node a[],edge b[],int n,int v){ a[v].flag=1; int i; for(i=0;i<neighbor[v].size();i++)//更新到相未选点的距离 { if(value[v][i]<a[neighbor[v][i]].value&&a[neighbor[v][i]].flag==0) { a[neighbor[v][i]].value=value[v][i]; a[neighbor[v][i]].parent=v; } } int min_value=inf,p=0; for(i=1;i<=n;i++)//找小距离，并选取 { if(min_value>a[i].value&&a[i].flag==0)//找到到未选节点的最小距离 { min_value=a[i].value; p=i;//记下所选下标 } } if(p==0);//没选取到最小距离，说明所有点都为已选集合，即最小生成树已完成 else { b[j].node1=a[p].parent; b[j].node2=p; b[j].value=min_value; j++; Prim(a,b,n,p); }}int main(){ node arr[max_size]; int n,m; cin>>n>>m;//输入节点数 n，边数 m for(int i=1;i<=n;i++)//初始化节点 { arr[i].flag=0;//初始化为未选 arr[i].value=inf;//初始化 从已选节点到该节点的距离为无穷大 } int a,b,c; for(int i=0;i<m;i++)//输入初始图 { cin>>a>>b>>c;//a b为边的节点，c为权值 neighbor[a].push_back(b);//把b装入a的邻居 value[a].push_back(c);//把对应权值装入 a的第i个邻居，对应第i个value值 neighbor[b].push_back(a); value[b].push_back(c); } edge mst[max_size];//用于装最小生成树 Prim(arr,mst,n,1);//1号节点开始 for(int i=0;i<n-1;i++) { cout<<mst[i].node1<<' '<<mst[i].node2<<' '<<mst[i].value<<endl; } return 0;}