菏泽建设企业网站/软文文案

1. 无回路
2. |v|个顶点一定有|v|-1条边

是生成树（向生成树中任加一条边都一定构成回路）

1. 包含全部顶点
2. |v|-1条边都在图里

边的权重和最小

贪心算法

“贪心”：每一步都要最好

“好”：权重最小的边

需要约束：只能用图里有的边，只能正海用掉|v|-1条边，不能有回路

prim算法——从根结点让一棵小树长大

下面用示意图来说明该算法：

首先以v1作为根结点

然后寻找与这棵树有关系的最小的边，所以将v1与v4的边收进来：

以v1和v4为基础再向外生长，有两种选择，v2和v3，先将v2收进来：

再将v3收进来：

继续看，不能将目前最小为3的边收进来，因为会构成回路，所以将v7收进来

然后将v6收进来：

最后将v5收进来：

void Prim()
{  MST={s};while(1){V=未收录顶点中dist最小值；if（这样的V不存在）break;将v收录进MST：dist[v]=0;for(V的每个邻接点 w）{ if(dist[w]!=0)if(E[v,w]<dist[w]){dist[W]=E[v,w];parent[W]=V;}}}if(MST中收录的顶点不到|V|个)cout<<"生成树不存在";}

Kruskal算法——将森林合并成树（更彻底的贪心）

每次将权重最小的边将其收进来，因此先将权重为1的边收录进来。

将每一个顶点视为一棵树，最后将其合并为一棵树，依次类推将权值为2的边收进来。直到生成n-1条边

算法实现：

void Kruskal(Graph G)
{   MST={};while(MST中不到|v|-1条边&&E中还有边}{从E中取一条权值最小的边E[V,W];//最小堆将E[V,W]从E中删除；if(E[V,W]不在MST中构成回路)//并查集将E[V,W]加入MST；else无视E[V,W];}if(MST中不到|V|-1条边)cout<<"生成树不存在"；
}