C++图学习整理

最小生成树

在无向图中生成一棵树（n-1条边，无环，连通所有点），且这棵树的劝和最小

普利姆算法（Prim）——加点法

任选一点开始，找到离这个点最近的点，加入最小生成树
再继续去找离这个最小生成树最近的点，加入最小生成树中，重复步骤2

克鲁斯卡尔算法（Kruskal） ——加边法

找到最短边，判断其两个端点在不在一个连通分量里
若在，则跳过；若不在，加入最小生成树

洛谷例题

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模：

对于 $20%$ 的数据，$N\le 5$，$M\le 20$。

对于 $40%$ 的数据，$N\le 50$，$M\le 2500$。

对于 $70%$ 的数据，$N\le 500$，$M\le 10^4$。

对于 $100%$ 的数据：$1\le N\le 5000$，$1\le M\le 2\times 10^5$，$1\le Z_i \le 10^4$。

样例解释：

所以最小生成树的总边权为 $2+2+3=7$。

#include<cstdio>   // 包含标准输入输出库
#include<queue>    // 包含优先队列库
#define INF 2147483647    // 定义无穷大（表示不可达距离）
#define MAXN 5001         // 定义最大节点数
#define MAXM 200001       // 定义最大边数
using namespace std;

// 全局变量
int head[MAXN], dis[MAXN];   // head：每个节点的邻接表的头指针，dis：节点到MST的最小距离
bool vis[MAXN];              // vis：标记节点是否已加入MST
int edge_sum = 0;            // 边计数
int n, m, MST;               // n：节点数，m：边数，MST：最小生成树的权重和

// 边结构体定义，存储边的目标节点及权重
struct Edge {
    int next, to, dis;
} edge[MAXM << 1];   // 使用两倍最大边数的数组，考虑无向图每条边存两次

// 添加边到邻接表
void addedge(int from, int to, int dis) {
    edge[++edge_sum].next = head[from]; // 设置新边的下一个指针为当前头指针
    edge[edge_sum].to = to;             // 设置目标节点
    edge[edge_sum].dis = dis;           // 设置边的权重
    head[from] = edge_sum;              // 更新头指针为新边的索引
}

// 优先队列中的节点结构体
struct node {
    int u, dis;  // u：节点编号，dis：距离
    // 重载运算符 <，使得优先队列按距离从小到大排序
    bool operator <(const node& rhs) const {
        return dis > rhs.dis;
    }
};

// Prim算法实现
void prim() {
    priority_queue<node> q;  // 优先队列，用于选择最小权重的边
    for (register int i = 0; i <= n; i++)  // 初始化所有节点的距离为无穷大
        dis[i] = INF;
    dis[1] = 0;              // 设置起始节点1的距离为0
    q.push((node{1, 0}));    // 将起始节点1加入优先队列

    while (!q.empty()) {
        node tmp = q.top();  // 取出距离最小的节点
        q.pop();
        int u = tmp.u, d = tmp.dis;
        if (vis[u]) continue;  // 如果节点已访问过，跳过
        vis[u] = 1;            // 标记节点u为已访问
        for (register int j = head[u]; j; j = edge[j].next) {  // 遍历邻接节点
            if (!vis[edge[j].to] && edge[j].dis < dis[edge[j].to]) {  // 如果邻接节点未访问且距离更短
                dis[edge[j].to] = edge[j].dis;  // 更新距离
                if (!vis[edge[j].to]) q.push((node){edge[j].to, dis[edge[j].to]});  // 将节点加入优先队列
            }
        }
    }
}

// 主函数
int main() {
    scanf("%d%d", &n, &m);  // 输入节点数和边数
    for (register int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);  // 输入边的起点、终点和权重
        addedge(x, y, z);   // 添加边
        addedge(y, x, z);   // 无向图需要添加两次（反向边）
    }
    prim();  // 执行Prim算法

    bool flag = 0;
    for (register int i = 1; i <= n; i++) {  // 检查所有节点是否都被访问过
        if (dis[i] == INF)
            flag = 1;   // 如果有节点未访问到，说明图不连通
        MST += dis[i];  // 累加MST的总权重
    }
    if (!flag) printf("%d\n", MST);  // 如果所有节点都访问到，输出MST的总权重
    else printf("orz\n");  // 否则输出"orz"，表示图不连通
    return 0;
}