最小生成树

prim算法

Prim算法求最小生成树
朴素版prim算法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e5+10;
int n,m;
int e[N*2],ne[N*2],h[N],w[N*2],idx; // 邻接表存储图
int dist[N];      // dist[i] 表示节点i到当前生成树的最小距离
bool st[N];       // st[i] 标记节点i是否已加入生成树

// 添加无向边
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

int prim()
{
    memset(dist,0x3f,sizeof dist); // 初始化所有距离为无穷大
    dist[1]=0;                     // 从节点1开始，距离设为0
    int t;
    int ans=0;                     // 存储最小生成树的总权重
    for(int i=0;i<n;++i)           // 循环n次，每次加入一个节点
    {
        t=-1;
        // 寻找未加入生成树中dist最小的节点
        for(int j=1;j<=n;++j){
            if(st[j]) continue;    // 跳过已加入的节点
            else if(t==-1||dist[j]<dist[t]) t=j; // 更新最小节点
        }
        // 如果最小距离仍是无穷大，说明图不连通
        if(dist[t]>=0x3f3f3f3f) return 0x3f3f3f3f;
        ans+=dist[t];             // 累加当前边的权重
        st[t]=true;               // 标记节点t已加入生成树（修正位置：在更新前标记）

        // 遍历节点t的所有邻接边
        for(int j=h[t];j!=-1;j=ne[j]){
            int k=e[j];           // 邻接节点k
            // 如果节点k未加入生成树且当前边权小于dist[k]，则更新
            if (!st[k] && dist[k] > w[j]) {
                dist[k] = w[j];
            }
        }
    }
    return ans;
}

int main()
{
    memset(h,-1,sizeof(h));      // 初始化邻接表头指针
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);              // 无向图添加双向边
        add(b,a,c);
    }
    int t=prim();
    if(t==0x3f3f3f3f) cout<<"impossible"<<endl;
    else cout<<t<<endl;
    return 0;
}

堆优化版prim算法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>  // 定义pair类型，用于存储(距离, 节点)

const int N = 1e5 + 10;     // 最大节点数
int n, m;                   // n: 节点数, m: 边数
int e[N * 2], ne[N * 2], h[N], w[N * 2], idx;  // 邻接表存储图
int dist[N];                // dist[i] 表示节点i到当前生成树的最小距离
bool st[N];                 // st[i] 标记节点i是否已加入生成树

// 添加无向边
void add(int a, int b, int c) {
    e[idx] = b;         // 存储边的终点
    w[idx] = c;         // 存储边的权重
    ne[idx] = h[a];     // 链表指针指向下一个节点
    h[a] = idx++;       // 更新头指针
}

// 优先队列优化的Prim算法
int prim() {
    memset(dist, 0x3f, sizeof dist);  // 初始化所有距离为无穷大
    priority_queue<PII, vector<PII>, greater<PII>> q;  // 小顶堆，存储(距离, 节点)
    q.push({0, 1});     // 从节点1开始，初始距离为0
    dist[1] = 0;        // 设置节点1的距离为0

    int ans = 0;        // 最小生成树的总权重
    int cnt = 0;        // 已加入生成树的节点数

    while (!q.empty()) {
        auto t = q.top();  // 获取堆顶元素（当前距离生成树最近的节点）
        q.pop();

        int dis = t.first;   // 当前节点到生成树的距离
        int ver = t.second;  // 当前节点编号

        // 如果节点已加入生成树，跳过重复处理
        if (st[ver]) continue;

        // 首次访问该节点：加入生成树
        ans += dis;         // 累加边权
        cnt++;              // 节点计数增加
        st[ver] = true;     // 标记节点已加入生成树

        // 遍历当前节点的所有邻接边
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];  // 邻接节点j

            // 如果邻接节点尚未加入生成树且当前边权小于已知最小距离
            if (!st[j] && dist[j] > w[i]) {
                dist[j] = w[i];          // 更新节点j到生成树的最小距离
                q.push({dist[j], j});    // 将更新后的距离和节点加入堆
            }
        }
    }

    // 如果加入的节点数不足n，说明图不连通
    if (cnt != n) return 0x3f3f3f3f;  // 返回特殊值表示无解
    return ans;  // 返回最小生成树总权重
}

int main() {
    memset(h, -1, sizeof h);  // 初始化邻接表头指针为-1
    cin >> n >> m;

    // 读入所有边并构建无向图
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);  // 添加a->b的边
        add(b, a, c);  // 添加b->a的边（无向图双向添加）
    }

    int t = prim();  // 执行Prim算法

    // 输出结果
    if (t == 0x3f3f3f3f) 
        cout << "impossible" << endl;  // 无生成树
    else 
        cout << t << endl;  // 输出权重总和

    return 0;
}

kruskal算法

Kruskal算法求最小生成树

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e5+10;  // 定义常量N，表示最大节点数
int n,m;             // n-节点数, m-边数

// 定义边的结构体，包含起点a、终点b和权重c
struct edge
{
    int a,b,c;
};
edge s[200010];  // 存储所有边的数组
int p[200010];   // 并查集父节点数组

// 边排序比较函数：按权重升序排列
bool cmp(edge a,edge b)
{
    return a.c<b.c;
}

// 并查集查找函数（带路径压缩）
int find(int a)
{
    if(p[a]!=a) 
        p[a]=find(p[a]);  // 递归查找并压缩路径
    return p[a];          // 返回根节点
}

// Kruskal算法实现最小生成树
int kruskal()
{
    sort(s+1,s+m+1,cmp);          // 按边权重升序排序
    for(int i=1;i<=n;i++) p[i]=i; // 初始化并查集

    int res=0;   // 存储最小生成树的总权重
    int cnt=0;   // 计数已选边的数量

    // 遍历所有边
    for(int i=1;i<=m;i++){
        int aa=s[i].a;  // 当前边的起点
        int bb=s[i].b;  // 当前边的终点
        int cc=s[i].c;  // 当前边的权重

        int pa=find(aa);  // 查找起点所在集合
        int pb=find(bb);  // 查找终点所在集合

        // 如果不在同一集合，则选择该边
        if(pa!=pb){
            p[pa]=pb;    // 合并集合
            res+=cc;     // 累加权重
            cnt++;       // 增加已选边计数
        }
    }

    // 判断连通性：最小生成树应有n-1条边
    if(cnt<n-1) 
        return 0x3f3f3f3f;  // 不连通时返回特殊值
    else 
        return res;         // 连通时返回总权重
}

int main()
{
    cin>>n>>m;  // 输入节点数和边数

    // 读入所有边
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        s[i]={a,b,c};  // 存储边信息
    }

    int t=kruskal();  // 调用Kruskal算法

    // 输出结果：不连通输出"impossible"，否则输出总权重
    if(t==0x3f3f3f3f) 
        cout<<"impossible"<<endl;
    else 
        cout<<t<<endl;

    return 0;
}