最小生成树的权怎么算,离散数学克鲁斯算法求最小生成树
最小生成树的权怎么算目录
关于离散数学中Kruskal生成最小生成树的一个白痴概念问题
最小生成树的权怎么算
最小生成树（Minimum Spanning Tree, MST）是一种用于连接一个无向连通图中的所有顶点的子图，使得所有边的权值之和最小。常用的最小生成树算法有 Kruskal 算法和 Prim 算法。
最小生成树的权值的计算是根据连接顶点的边的权值来决定的。边的权值通常是连接两个顶点之间的距离、费用或其他度量值。
以 Kruskal 算法为例，它的步骤如下：
1. 将图中的所有边按照权重进行排序。
2. 从权重最小的边开始，逐个选择边，并检查它是否与已选择的边构成环。如果没有环，则将该边添加到最小生成树中。
3. 重复步骤2，直到选择了 n-1 条边（n 是顶点的数量）。
最小生成树的权值就是这 n-1 条边的权值之和。因此，要计算最小生成树的权值，你需要：
1. 确保图是无向连通的。
2. 找到一个最小生成树算法（如 Kruskal 或 Prim）。
3. 使用该算法计算最小生成树。
4. 计算最小生成树中所有边的权值之和。
注意：在实际应用中，可能会对计算出的最小生成树进行一些优化或调整，以确保更高效的性能或满足特定需求。
离散数学克鲁斯算法求最小生成树
克鲁斯算法求最小生成树基本思路简而言之就是找边1）找权值最小的边2）假设选择，判断是否形成环路，如果是，则把权赋值为极大值，否则确认选择3）重复做1），2），直到所有的结点联通
急求！请问如何用最小堆实现prim算法来求最小生成树权值？
用邻接矩阵存储图。
#include<iostream>
#include<sstream>
using namespace std;
typedef pair<int,int>P;//无序对，堆中存的是无序对，第一个表示节点，第二个表示节点对应的最短路径值
const int MAX=100;
int mind[MAX];//最短距离
const int MAXN=1000000;
int path[MAX];//路径
int s,t,n,m;
int vis[MAX];//是否已经遍历过
int g[MAX][MAX];
class Heap
{
public:
P elem[MAX];
int n;
Heap(){n=0;}
void ins(P e);
P del();
int num();
};
void Heap::ins(P e)
{
int p;
for(p=++n;p>1&&e.second<elem[p>>1].second;elem[p]=elem[p>>1],p>>=1);//与父结点比较，父结点大的话交换
elem[p]=e;
}
P Heap::del()//删除一个元素，并保持最小堆的性质
{
int i=1,j;
P e=elem[1];
for(j=2;j<n;j<<=1)
{
if(j<n-1&&elem[j].second>elem[j+1].second) j=j+1;//删第一个，较小的孩子成为新的根
if(elem[n].second>elem[j].second)
{
elem[i]=elem[j];
i=j;
}
else break;
}
elem[i]=elem[n--];
return e;
}
int Heap::num()
{
return n;
}
int main()
{
while(cin>>n>>m)
{//分别是边的个数和顶点的个数
vector<vector<Edge> >v(m);//保存各个点的连接情况，每个一维向量是与该点的各个相连的边
int i,j;
for(i=0;i<m;i++)
for(j=0;j<m;j++)
g[i][j]=MAXN;
for(i=0;i<n;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=c;
g[b][a]=c;
}
Heap h;
h.n=0;
P e;
for(i=0;i<m;i++)
{
mind[i]=MAXN;
vis[i]=0;
path[i]=-1;
}
s=0;
mind[e.first=s]=e.second=0;
h.ins(e);
int res=0;
while(h.num())
{
e=h.del();
int j=e.first;
if(!vis[j])
{
vis[j]=1;
res+=e.second;
for(i=0;i<m;i++)
{//relax（）
if(i!=j&&!vis[i]&&mind[i]>g[j][i])
{
mind[i]=g[j][i];
path[i]=j;
e.first=i;
e.second=mind[i];
h.ins(e);
}
}
}
}
cout<<"最小生成树权值："<<res<<endl;
}
}
关于离散数学中Kruskal生成最小生成树的一个白痴概念问题
边的权重是算法的输入(input)
举个例子 假设我们要把N个城市连起来，使修路的总距离最短。
这时计算MST 边的权重就是两个城市间的距离
