1. 树与图的存储

• 图的顶点个数为n，边的个数为m

$O(n) = O(m)$，稀疏图，邻接表存储

// h[k]指向结点k的所有1阶邻居组成的链表的头结点
int h[N], e[N], ne[N], idx;

// 初始状态没有边相连
memset(h, -1, sizeof h);

// 插入有向边(a, b)
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

$O(n^2) = O(m)$，稠密图，邻接矩阵存储

void add(int a, int b) {
    g[a][b] = g[b][a] = 1; //无向图
    g[a][b] = 1; // 有向图
}

2. 树与图的遍历

深度优先遍历（DFS）

/*=========================================================*\
| DFS O(n + m)
| 定义标记数组st，下标表示结点编号，值表示该结点是否被访问过；
| 从某个结点开始，一条路走到黑，到头了再回溯；
| 整个过程每个点只会被访问一次
\*=========================================================*/
int h[N], e[N], ne[N], idx;
bool st[N];

void dfs(int u) {
    st[u] = true;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

树的重心

#include <iostream>
#include <cstring>
using namespace std;

const int N = 2e5 + 10; // 无向图，边的条数应该开结点个数的2倍

int h[N], e[N], ne[N], idx; // 邻接表
int n, ans = N; // 答案
bool st[N];

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

// 返回以u为根的树的结点个数
int dfs(int u) {
    st[u] = true;
    // 当枚举到结点u时，把u删除后，剩余连通块中结点数最大是ret
    int sum = 1, ret = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            int s = dfs(j); // 各个子树的节点个数
            sum += s;
            ret = max(ret, s);
        }
    }
    ret = max(ret, n - sum);
    ans = min(ans, ret);
    return sum;
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ ) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1);
    cout << ans;
    return 0;
}

例子：排列数字

例子：n皇后

广度优先遍历（BFS）

/*============================================================================*\
| BFS O(n + m)
| 从某个结点开始，依次访问它的一阶邻居、二阶邻居，直到没有结点可以继续访问为止；
| 整个过程每个点只会被访问一次
\*============================================================================*/
int h[N], e[N], ne[N], idx;
bool st[N];
queue<int> q;

void bfs() {
    st[0] = 1;
    q.push(0);
    while (!q.empty()) {
        int t = q.front(); q.pop();
        // options...
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                st[j] = 1;
                q.push(j);
            }
        }
    }
}

图中点的层次

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
int d[N], n, m;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

int bfs() {
    memset(d, -1, sizeof d);
    d[1] = 0;
    queue<int> q;
    q.push(1);
    while (q.size()) {
        int t = q.front(); q.pop();
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1) {
                q.push(j);
                d[j] = 1 + d[t];
            }
        }
    }
    return d[n];
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ ) {
        int a, b; cin >> a >> b;
        add(a, b);
    }
    cout << bfs();
    return 0;
}

例子：走迷宫

例子：八数码

3. 拓扑排序

/*=============================================================*\
| Topsort O(n + m)
| 将所有初始入度为0的点入队；
| 每当队中的点加入到拓扑序列里，就把与当前点相连的点的入度减一；
| 只要产生了入度为0的点，就把它加入队列
\*=============================================================*/
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx; // 邻接表
int d[N]; // 记录点的入度
int n, m;
vector<int> top; // 拓扑序列

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

bool bfs() {
    queue<int> q;
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q.push(i);
    while (q.size()) {
        int t = q.front(); q.pop();
        top.push_back(t);
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j] -- ;
            if (!d[j]) {
                q.push(j);
            }
        }
    }
    return top.size() == n;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ ) {
        int a, b; cin>> a >> b;
        add(a, b);
        d[b] ++ ;
    }
    if (bfs()) {
        for (auto x : top) cout << x << ' ';
    } else {
        cout << -1;
    }
    return 0;
}

4. 最短路算法

朴素Dijkstra

/*============================================================================*\
| Dijkstra O(n^2 + m)
| 步骤：
| 1. 建图，注意重边和自环，适合稠密图；
| 2. 初始化dist数组；
| 3. 迭代n次
|       （1）找到当前未确定最短距离的点中距离最小的点t；
|       （2）修改点t的状态（st）
|       （3）用点t更新所有点的最短距离（点1到所有点的最短距离是否要经过点t）
| 4. 如果dist[n]的值为无穷大，说明点1无法到达点n，不存在最短路；否则dist[n]就是答案
\*============================================================================*/
#include <iostream>
#include <cstring>
using namespace std;

const int N = 510;

int g[N][N]; // 由数据范围得出图是稀疏还是稠密
int dist[N]; // 存储点1到所有点的最短距离
bool st[N]; // 点的最短距离是否已经确定
int n, m;

int dijkstra() {
    memset(dist, 0x3f, sizeof dist); // init，初始状态点1到所有点的距离是正无穷
    dist[1] = 0; // 点1到自己的最短距离确定是0
    for (int i = 0; i < n; i ++ ) {
        int t = -1;
        for (int j = 1; j <= n; j ++ ) {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = true;
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < m; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    cout << dijkstra();
    return 0;
}

堆优化版Dijkstra

/*============================================================================*\
| Dijkstra O(mlog(n))
| 步骤：
| 1. 建图，注意重边和自环，适合稀疏图；
| 2. 初始化dist数组；
| 3. 迭代n次
|       （1）找到当前未确定最短距离的点中距离最小的点t；（用最小堆优化查找）
|       （2）修改点t的状态（st）
|       （3）用点t更新邻接点的最短距离（不跟点t直接相连的点最短距离一定不会被更新）
| 4. 如果dist[n]的值为无穷大，说明点1无法到达点n，不存在最短路；否则dist[n]就是答案
\*============================================================================*/
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];
int n, m;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0, 1});

    while (q.size()) {
        PII t = q.top(); q.pop();
        int dis = t.first, v = t.second;
        if (st[v]) continue;
        st[v] = true;
        for (int i = h[v]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dis + w[i]) {
                dist[j] = dis + w[i];
                q.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ ) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << dijkstra();
    return 0;
}

Bellman-Ford

边权可能为负数, 存在负权回路, 最多经过k条边

/*===================================================================================*\
| BellmanFord O(mn)
| 1. backup数组是上一次迭代的dist数组的备份，由于是每个点同时向外出发，
| 因此需要对dist数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点;
| 2. 只要存在负权回路，经过n次迭代，最短路径一定还会更新，因为可以沿着这条回路一直转圈，
| 把这条路径后的点的最短距离更新成负无穷
\*===================================================================================*/
#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, M = 1e4 + 10;

struct Edge {
    int a, b, w;
} edges[M];

int dist[N], backup[N];
int n, m, k;

void bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < k; i ++ ) {
        memcpy(backup, dist, sizeof backup);
        for (int j = 0; j < m; j ++ ) {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], backup[e.a] + e.w);
        }
    }

    if (dist[n] >= 0x3f3f3f3f / 2) puts("impossible");
    else cout << dist[n];
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i ++ ) {
        int a, b, w; cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    bellman_ford();
    return 0;
}

SPFA

边权可能为负数, 不存在负权回路

/*===================================================================================*\
| SPFA O(km)
| BellmanFord的队列实现，减少不必要的冗余计算；
| 前一次松弛中改变了最短距离的点，才会引起它们的邻接点的最短距离的改变
\*===================================================================================*/
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];
int n, m;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

void spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    st[1] = true;
    queue<int> q;
    q.push(1);
    while (q.size()) {
        int t = q.front(); q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) puts("impossible");
    else cout << dist[n];
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ ) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);
    }
    spfa();
    return 0;
}

Floyd

/*======================================================*\
| Floyd O(n^3)
| 基于动态规划，枚举可能经过的点k更新i和j之间的最短距离
\*======================================================*/
#include <iostream>
using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int g[N][N];
int n, m, k;

void floyd() {
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

int main() {
    cin >> n >> m >> k;
    // 初始化
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) g[i][j] = 0;
            else g[i][j] = INF;

    for (int i = 0; i < m; i ++ ) {
        int x, y, z; cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
    }
    floyd();
    for (int i = 0; i < k; i ++ ) {
        int x, y; cin >> x >> y;
        if (g[x][y] >= INF / 2) puts("impossible");
        else cout << g[x][y] << endl;
    }
    return 0;
}

5. 最小生成树算法

朴素Prim

// 稠密图
const int N = 510, INF = 0x3f3f3f3f;

int g[N][N], dist[N]; // 邻接矩阵/点到最小生成树集合的距离（Dijkstra是到点1的距离）
bool st[N]; // 点是否已经加入到集合中
int n, m;

int prim() {
    memset(dist, 0x3f, sizeof dist);
    int ret = 0;
    for (int i = 0; i < n; i ++ ) {
        // 查找集合外的距离最小的点
        int t = -1;
        for (int j = 1; j <= n; j ++ ) {
            if (!st[j] && (t == - 1 || dist[j] < dist[t]))
                t = j;
        }
        st[t] = true;
        // 至少迭代了一轮的前提下，还存在点到集合的距离是无穷大，说明图不是连通的
        if (i && dist[t] == INF) return INF;
        if (i) ret += dist[t];
        // 更新其他点到集合的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);
    }
    return ret;
}

Kruskal

/*========================================================================================*\
| Kruskal O(mlog(n))
| 步骤：
| 1. 所有边按边权从小到大排序；
| 2. 从小到大枚举每一条边，边的两个端点不在一个集合中，则将它们所在集合合并，合并代价为边权；
| 3. 合并次数不够n-1次，说明图不是连通的。
\*========================================================================================*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

struct Edge {
    int u, v, w;
    bool operator< (const Edge &e) const {
        return w < e.w;
    }
} edges[M];

int p[N];
int n, m;

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void kruskal() {
    sort(edges, edges + m);
    int ret = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int r_u = find(u), r_v = find(v);
        if (r_u != r_v) {
            p[r_u] = r_v;
            ret += w;
            cnt ++ ;
        }
    }
    if (cnt < n - 1) puts("impossible");
    else cout << ret;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) {
        int u, v, w; cin >> u >> v >> w;
        edges[i] = {u, v, w};
    }
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    kruskal();
    return 0;
}

6. 二分图算法

染色法

/*======================================*\
| 染色法
| 一个图是二分图当且仅当图中不含奇数环
| 奇数环：环中含有奇数条边
\*======================================*/
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

int h[N], e[M], ne[M], idx; // 邻接表
int color[N]; // 0表示没有染色，1和2表示两种染色方式
int n, m;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

bool dfs(int u, int x) {
    color[u] = x;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!color[j]) {
            if (!dfs(j, 3 - x)) return false;
        } else if (color[j] == x) return false;
    }
    return true;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h); // 初始化
    for (int i = 0; i < m; i ++ ) {
        int a, b; cin >> a >> b;
        add(a, b), add(b, a);
    }
    bool flag = true;
    // 从1~n依次染色
    for (int i = 1; i <= n; i ++ ) {
        if (!color[i]) {
            if (!dfs(i, 1)) { // 染色冲突说明不是二分图
                flag = false;
                break;
            }
        }
    }
    if (flag) puts("Yes");
    else puts("No");
    return 0;
}

匈牙利算法

/*===============================================================================================*\
| 二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，
| 则称M是一个匹配。
| 二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
\*===============================================================================================*/
#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, M = 1e5 + 10;

int h[N], e[M], ne[M], idx; // 邻接表
int match[N]; // match[i] = j: i是[1, n2]中的点, j是[1, n1]中的点
bool st[N]; // 集合（1~n2）的访问情况
int n1, n2, m;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

bool find(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            st[j] = true;
            if (!match[j] || find(match[j])) {
                match[j] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ ) {
        int u, v; cin >> u >> v;
        add(u, v);
    }
    int ret = 0;
    for (int i = 1; i <= n1; i ++ ) {
        memset(st, false, sizeof st);
        if (find(i)) ret ++ ;
    }
    cout << ret;
    return 0;
}