定义
图的存储
图的遍历
- 深度优先搜索DFS
  - 邻接矩阵模板
  - 邻接表模板
- 广度优先搜索遍历BFS
  - 邻接矩阵版模板
  - 邻接表版模板
最短路径
最小生成树
- Prim
- Kruscal
二分图
- 染色法
- 匈牙利算法

定义

顶点（Vertex）和边（Edge），顶点和边都可以具有一定的属性（权值），点权、边权
符号：G(V, E)
分类：

无向图
- 连通：两个顶点互相可达则为连通
- 连通图：如果图的任意两个顶点均连通，则该图为连通图，否则为非连通图
- 连通分量：非连通图中的极大连通子图为连通分量
有向图
- 强连通：两个顶点各自可以通过一条有向路径达到另一个顶点
- 强连通图：任意两个顶点强连通为强连通图，否则为非强连通图。
- 强连通分量：非强连通图中极大强连通子图为强连通分量
  图的存储
  度：
入度
出度

邻接矩阵：将图的边的信息存储在二维数组中，可以用边权为0（-1、很大的数等等）表示不存在路径

邻接表：将每个顶点的出边单独存储到一个链表（或者可变长数组如vector)中，这个列表称作邻接表

图的遍历

深度优先搜索DFS

遍历图时沿着一条路径走到黑，然后再退回
遍历图的时候，需要一个连通块一个连通块的遍历，如果已知图是连通图，那么一次遍历即可。

邻接矩阵模板

const int MAXV = 1000; // 最大顶点数
int n; // 顶点数
int G[MAXV][MAXV];
bool visited[MAXV] = {false}; // 记录顶点是否访问过
void dfs(int u, int depth) { // 遍历一个连通块
    visited[u] = true; // 标记已经访问过
    // code 对顶点的操作
    // 枚举u能到达的所有顶点
    for (int v = 0; v < n; v++) {
        if (visited[v] == false && G[u][v] != INT32_MAX) { // 这里用INT32_MAX表示不存在路径
            dfs(v, depth + 1);
        }
    }
}
void dfsTrave() {
    for (int u = 0; u < n; u++) { // 遍历整个图
        if (visited[u] == false) {
            dfs(u, 1); // 访问u和u所在的连通块
        }
    }
}

邻接表模板

const int MAXV = 1000; // 最大顶点数

int n; // 顶点数
vector<int> Adj[MAXV];

bool visited[MAXV] = {false}; // 记录顶点是否访问过

void dfs(int u, int depth) {
    visited[u] = true; // 标记已经访问过
    // code 对顶点的操作

    // 枚举u能到达的所有顶点
    for (int i = 0; i < Adj[u].size(); i++) {
        int v = Adj[u][i];
        if (visited[v] == false) { // 这里用INT32_MAX表示不存在路径
            dfs(v, depth + 1);
        }
    }
}

void dfsTrave() {
    for (int u = 0; u < n; u++) {
        if (visited[u] == false) {
            dfs(u, 1); // 访问u和u所在的连通块
        }
    }
}

广度优先搜索遍历BFS

广度优先搜索就是以扩散的方式访问节点，访问一节点，将其所有可达的节点都访问完在访问下一层，与树的层序遍历一样，需要用队列来实现BFS
访问一个顶点时，将该顶点周围的所有未入队的顶点入队

邻接矩阵版模板

const int MAXV = 1000; // 最大顶点数

int n, G[MAXV][MAXV];
bool inq[MAXV] = {false}; // 记录顶点是入过队

void bfs(int u) {
    queue<int> q;
    q.push(u);
    inq[u] = true; // 标记已经入过队

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // code 对顶点的操作 

        // 枚举u能到达的所有顶点
        for (int v = 0; v < n; v++) {
            if (inq[v] == false && G[u][v] != INT32_MAX) {
                q.push(v);
                inq[v] = true;
            }
        }
    }
}

void bfsTrave() {
    for (int u = 0; u < n; u++) {
        if (inq[u] == false) {
            bfs(u); // 访问u和u所在的连通块
        }
    }
}

邻接表版模板

const int MAXV = 1000; // 最大顶点数

int n; // 顶点数
vector<int> Adj[MAXV];

bool inq[MAXV] = {false}; // 记录顶点是入过队

void bfs(int u) {
    queue<int> q;
    q.push(u);
    inq[u] = true; // 标记已经入过队

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // code 对顶点的操作 

        // 枚举u能到达的所有顶点
        for (int i = 0; i < Adj[u].size(); i++) {
            int v = Adj[u][i];
            if (inq[v] == false) {
                q.push(v);
                inq[v] = true;
            }
        }
    }
}

void bfsTrave() {
    for (int u = 0; u < n; u++) {
        if (inq[u] == false) {
            bfs(u); // 访问u和u所在的连通块
        }
    }
}

在给定BFS初始点的情况下，可以通过BFS得到其他顶点的层号，这时只需要修改一下模板就可以。

最短路径

如果图的边权都是1的话，最短路径问题是可以通过BFS来解决的，如果边权不是1，那么需要通过下面的算法来解决最短路径问题。

下面的题目都是用静态链表存储邻接表
图 - 图3
i -> {e[i], ne[i], w[i]}：

i 指向的节点是e[i]
i -> e[i] 的边权是w[i]
ne[i]指向下一个i指向的节点

Dijkstra

Dijkstra算法采用的是一种贪心的策略，声明一个数组dist来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合st，
算法流程：
初始化源点，假设为节点1，dist[1] = 0; 初始化源点到其他节点的距离，为正无穷大。
遍历所有节点：从所有不在集合st中的点找到距离源点最近的点，用它更新所有能够到达达的节点距离源点的距离，然后将此节点放入st中，表示已经找到源点至该点的最短路径。
当所有的节点都加入st后，通过dist数组可以得到从源点到任意点的最短路径。

朴素Dijkstra算法

图中节点的边权使用邻接矩阵来存储，时间复杂度为O(N^2)，邻接矩阵存储图适用于稀疏图
题目链接

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510; // 最多500个点
int dist[N], g[N][N]; // 用邻接矩阵来存储边和权
int n, m;
bool st[N]; // true表示已经算完距离源点的最短路径


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

    for (int i = 1; i < n; i++) { // 遍历所有节点
        int t = 0;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == 0 || dist[t] > dist[j])) // 找到为加入集合中的节点中距离源点最近的节点
                t = j;
        }
        // 用这个节点更新它所能到达节点距离源点的最短距离
        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
        st[t] = true;
    }
    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() << endl;
    return 0;
}

堆优化版的Dijkstra算法

题目链接
因为每次更新节点时，都是使用未在st集合中的节点中距离源点距离最小的节点，那么可以维护一个小根堆，更新路径长度的时候直接使用堆头而不用遍历一遍查找节点。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int N = 1e6 + 10;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];
int n, m;

typedef pair<int, int> PII;

void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c; // a->b 的边权是c
    h[a] = idx++;
}

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dist[1] = 0;
    q.push({0, 1}); // 将距离设为first，堆排序按照first来排
    while (!q.empty()) {
        auto t = q.top();
        q.pop();

        int node = t.second;
        if (st[node]) continue;

        for (int i = h[node]; i != -1; i = ne[i]) { // 更新所有能到达的节点
            int j = e[i];
            if (dist[j] > dist[node]+ w[i]) { //w[i]是node->e[i]的边权
                dist[j] = dist[node] + w[i];
                q.push({dist[j], j});
            }
        }
        st[node] = true;
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}


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

Bellman-Ford

题目链接
在不超过k条边的情况下，找到由源点至目标点的最短路径，边权可以为负。这个算法就是暴力搜索

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 510, M = 10010;
int n, m, k;
int dist[N], last[N]; // last数组用来记录上一次更新的结果，为了避免串联发生而导致经过的边数超过k条

struct Edges {
    int a, b, c;
}edges[M];

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

    for (int i = 0; i < k; i++) { // 每迭代一次，就是多使用一条边
        memcpy(last, dist, sizeof dist); // 拷贝上一次的结果
        for (int j = 0; j < m; j++) { // 遍历每一条边
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c); // 使用上一次更新的结果更新最短距离
        }
    }
    if (dist[n] >= 0x3f3f3f3f / 2) return false;
    return true;
}

int main() {

    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    bool bf = bellman_ford();
    if (!bf) puts("impossible");
    else cout << dist[n] << endl;
    return 0;
}

SPFA算法

SPFA算法是对bellman-ford算法的优化，当一个节点更新后到源点的最短路径变短，那么将其加入队列，后面会用它来更新它所能到达的其他节点的最短路径。有点像Dijkstra

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;
int h[N], e[N], ne[N], w[N], idx; // 图
int n, m;
int dist[N];
bool st[N]; // st标记的是队列中是否已经存在某节点，放置队列中的节点重复

void add(int a, int b, int c) { // a->b 边权为c
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool spfa() {
    memset(dist, 0x3f, sizeof dist);
    queue<int> q; // 队列中的元素用于更新最短路径长度
    q.push(1);
    dist[1] = 0;
    st[1] = true; // 将节点1入队，置为true


    while (!q.empty()) {
        int t = q.front(); q.pop();
        st[t] = false; // 节点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]) {
                    q.push(j);
                    st[j] = true; // 节点j入队，置为true
                }
            }
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return false;
    return true;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if (!spfa()) puts("impossible");
    else cout << dist[n] << endl;
    return 0;
}

Floyd

基于动态规划的思想求多源最短路径
算法框架

void floyd() {
    for (int k = 1; k <= n; k ++ ) // 每次以k为中转，看一下是否能够得到从点i到j的更短的路径
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

初始d[i][j]表示节点i和节点j的边和边权，经过floyd处理后，d[i][j]是节点i到节点j之间的最短路径长度
题目链接

最小生成树

图 - 图4

Prim

与Dijkstra算法类似，用一个集合存储已经加入最小生成树的节点，每次迭代，从未加入集合的点中选择距离集合最近的点，将其加入集合

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N];
int dist[N]; // 每个节点距离集合的距离
int n, m;
bool st[N];

int prim() {
    memset(dist, 0x3f, sizeof dist); // 初始化到集合的距离都为无穷大
    int res = 0; // 记录最小声成树的边权之和
    for (int i = 0; i < n; i++) { // 迭代n次，最小生成树要包括所有节点
        int t = 0;
        for (int j = 1; j <= n; j++) { // 从未加入集合的点中找到距离集合最近的点
            if (!st[j] && (!t || dist[t] > dist[j]))
                t = j;
        }
        if (i && dist[t] == INF) return INF; // 如果最近的点是INF说明不连通，直接返回
        if (i) res += dist[t]; // 记录所选边的长度, 如果只选择了一个点则没有边
        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], g[t][j]);
        }
        st[t] = true; 
    }
    return res;
}

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] = g[b][a]= min(g[a][b], c);
    }

    int t = prim();
    if (t == INF) puts("impossible");
    else cout << t << endl;
    return 0;
}

题目链接
对比一下Dijkstra算法：

Dijkstra算法每次从未加入集合中的点中选择距离源点最近的点，并用它更新所有点距离源点的距离
Prim算法每次从未加入集合中的点选择距离集合最近的点，选择后更新所有点距离集合的距离

堆优化版Prim就是把选择最近距离的过程使用堆来维护，用的比较少，一般稀疏图选择使用克鲁斯卡尔（kruscal）算法

Kruscal

Kruscal算法的基本思想：维护一个集合表示加入最小生成树的节点。将所有的边按照权值排序，每次选择最短的边，如果最短的边两端的节点没有在同一个集合中，将其合并（并查集）。
最后如过表示最小生成树的集合包括图中的所有节点，那么就得到了最小生成树，否则表示图不连通，没有最小生成树。

自边和重边：因为每次选择最短的边，所以有重边的话也是优先按照最短的那一条边处理，自边的节点是属于一个集合，不会加入到最小生成树中

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010, M = 200010, INF = 0x3f3f3f3f;
int n, m;
int p[N];

struct Edges {
    int a, b, w;
    bool operator< (Edges& e) { return w < e.w; }
}edges[M];
// 并查集find函数
int find(int u) {
    if (p[u] != u) p[u] = find(p[u]); // 路径优化
    return p[u];
}

int kruscal() {
    // 初始化并查集
    for (int i = 1; i <= n; i++) p[i] = i;
    sort(edges, edges + m);

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i++) { // 从小到大枚举边
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a);
        b = find(b);
        if (a != b) { // 如果a和b不在一个集合中，合并两个集合
            p[a] = b;
            res += w;
            cnt++;
        }
    }
    if (cnt < n - 1) return INF; // 如果最小生成树中边的个数小于n-1, 返回
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }

    int t = kruscal();
    if (t == INF) puts("impossible");
    else cout << t << endl;
    return 0;
}

题目链接

二分图

图 - 图5
二分图的概念
无向图是二分图的充分必要条件：至少有两个节点，且所有的回路都是偶数个节点

染色法

染色法可以判断一个图是否为二分图，一个节点染黑色，与它相连的节点染为白色，如果没有奇数环，那么染色一定不会冲突（一个节点染不同颜色），

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;
int h[N], e[M], ne[M], idx;
int n, m;
int color[N];

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

bool dfs(int u, int c) {
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i]) { // 给所有与u相连的点染色
        int j = e[i];
        if (!color[j]) {
            if (!dfs(j, 3 - c)) return false;
        } else if (color[j] == c) return false;
    }
    return true;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a); // 无向图
    }
    bool flag = true;
    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;
}

题目链接

匈牙利算法

匈牙利算法的概念
匈牙利算法可以求二分图的最大匹配数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010;
int h[N], e[M], ne[M], idx;
int n1, n2, m;
int match[N]; // 记录与n2中的节点匹配的n1节点
bool st[N]; // 防止重复搜索n2中的一个节点

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

bool find(int x) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            st[j] = true; // 标记一下这个节点已经试过了，无法匹配
            if (match[j] == 0 || find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h); // 初始化
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    int res = 0;
    for (int i = 1; i <= n1; i++) {
        memset(st, false, sizeof st);
        if (find(i)) res++; // 成功匹配
    }
    cout << res << endl;
    return 0;
}

题目链接

图

定义

图的存储

图的遍历

深度优先搜索DFS

邻接矩阵模板

邻接表模板

广度优先搜索遍历BFS

邻接矩阵版模板

邻接表版模板

最短路径

Dijkstra

朴素Dijkstra算法

堆优化版的Dijkstra算法

Bellman-Ford

SPFA算法

Floyd

最小生成树

Prim

Kruscal

二分图

染色法

匈牙利算法