最小生成树

prim

/*
这里和Dij的区别为d[u]代表着两个集合之间的最小值
因此每次在选好一个u时 需要更新d[u]的值 这也就是和dij不同的一点
这里vis是否访问 可以认为是否置于S集合中
*/
int prim(int root){

    fill(d,d+maxn,inf);
    d[root] = 0;//自身到自身为0
    int ans = 0;// 存放最小的边权之和 返回的结果
    for(int i = 0;i<n;i++)
    {
        //每次循环在里面找到最小的一个u
        int u = -1;
        int mx = inf;
        for(int j = 0;j<maxn;j++)
        {
            // 这里需要判断这个结点是否访问过呢 肯定需要 不然一直选择起点
            if(mx > d[j] && vis[j]==0)
            {
                mx = d[j];
                u = j;
            }
        }
        if(u == -1) return -1;//找不到最小 结束
        vis[u] = 1;//代表已经加入集合
        ans += d[u];
        cout << u <<" ";// 这是依次加入的结点
        //需要更新d的值 以u为中介看看是否可以更新距离
        // 实际上这里就是遍历u的邻居结点 这里是可以优化性能的地方 也可以进行二次比较

        for(int v = 0;v<n;v++)
        {
            // v未访问 u可以到v 以u为中介可以使u到达S更近
            // 因为是集合的概念 因此直接修改成mp[u][v]即可
            // 需要注意mp初始化必须其余元素为inf才可
            if(vis[v] == 0 && mp[u][v] != inf && mp[u][v] < d[v]) {
                d[v] = mp[u][v];
                // cout << d[v] <<" ";
            }
        }
    }
    return ans;
}

kruskal

/*
kruskal 采用边贪心
1.将所有边权排序
2.按边权从小到大测试所有边,如果两个点不在一个连通块,就合并
3.直到边数等于总结点-1 合并完成
而对于边权的排序 则需要结构体排序
利用并查集来判断是否处于同一个连通块
*/
struct edge{
    int u,v;// 首尾结点
    int cost; //边权
}Edge[maxn];

// 根据权值小的排序
bool cmp(edge a,edge b){
    return a.cost < b.cost;
}

int fa[maxn];

// 找x的父亲 路径压缩
int Find(int x)
{
    if(x==fa[x]) return x;
    int t = Find(fa[x]);
    fa[x] = t;
    return t;
}

// 合并两个孩子
int Union(int a,int b)
{
    int Fa = Find(a);
    int Fb = Find(b);
    fa[Fa] = Fb;
}

int kruskal()
{
    sort(Edge,Edge+m,cmp);
    for(int i = 0;i<n;i++){
        fa[i] = i;
    }
    int ans = 0,num = 0;
    //遍历所有边
    for(int i = 0;i<m;i++)
    {
        edge temp = Edge[i];
        int u = temp.u;
        int v = temp.v;
        int cost = temp.cost;
        if(Find(u)!=Find(v)){
            Union(u,v);
            num ++;
            ans += cost;
        }
    }
    if(num != n-1) return -1;
    return ans;
}