图论合集

图论这里我们先是了解其概念、几个算法即可

遍历： dfs、bfs

下文中的知识点属于提高组考点

最短路：

• 无负权：dijkstra
• 有负权：bellman_ford、spfa、floyed

并查集：

• 合并两个不同的集合
• 查询元素的祖先

int p[N];
void init(int n){ // 初始化， p[i]=i 自己是自己的父亲
    for(int i=0; i<=n; i++) p[i]=i;
}
int find(int u){ // 查询 u 的父亲
    return u==p[u] ? u:p[u]=find(p[u]);
}
void merge(int u,int v){ // 合并 u，v，使得其为同一个家族
    int a=find(u), b=find(v);
    p[a] = b;
}

最小生成树：

• kruskal：每次选择权值最小的边，利用并查集进行合并。

• 步骤：

• 1. 将数据保存为边集数组/边的集合；
  2. 按照边的权值进行升序排序；
  3. 每次选择最小的边，查询该边连接的两个顶点 $u,v$ 是否在同一集合，如果不在同一集合就将其合并为一个集合，如果在同一集合就不管；
  4. 重复步骤3，直到选择的边的数量为点数减 $1$（因为树的边数 $m$，点数为 $n$，有 $m=n-1$）。

• 例题：P1568 最小生成树

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, M = 5e5 + 10;
int n, m, p[N];
LL ans; // 总边全爆int

struct T {
    int u, v, w; // 按照边权升序排序
    bool operator<(const T& t) const { return w < t.w; }
} g[M << 1];
int find(int u) {// 查询 u的祖先
    return u == p[u] ? u : p[u] = find(p[u]);
}
int main() {
    cin >> n >> m;
    int u, v, w;
    for (int i = 0; i <= n; i++) p[i] = i;// 初始化自己是自己的祖先
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w; // 无向图
        g[i] = {u, v, w}, g[m + i] = {v, u, w};
    }
    m <<= 1; // 等同 m*=2, 无向图，边的数量*2
    sort(g + 1, g + 1 + m);
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        int u = g[i].u, v = g[i].v, w = g[i].w;
        int a = find(u), b = find(v);
        if (a != b) p[a] = b, ans += w, cnt++; // 不在同一集合，进行合并
        if (cnt == n - 1) break; // 确定答案，以后的边都不会被选，直接退出
    }
    cout << ans;
}