devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

常用算法代码模板 (3) ：搜索与图论

作者：小小林熬夜学编程 | 2024-05-21 04:37:36

赞

踩

常用算法代码模板 (3) ：搜索与图论

AcWing算法基础课笔记与常用算法模板 (3) ——搜索与图论

算法模板系列文章目录
常用算法代码模板 (1) ：基础算法
常用算法代码模板 (2) ：数据结构
常用算法代码模板 (3) ：搜索与图论
常用算法代码模板 (4) ：数学知识
算法选择——由数据范围反推算法时间复杂度

文章目录

0 搜索技巧

  • DFS
    • 分析问题：画图、归纳
    • 保存现场
    • 剪枝
  • BFS
    • 必要时开距离数组记录第一次到达每个点时的距离（即为到达每个点的最短路距离）
    • 求多源最短路时，可以设立一个超级源点（指向各源点的出边权值为0），则将问题转化为从超级源点到终点的单源最短路径。实际用BFS求时只需在初始化时将所有源点一次性入队即可。

偏移量

控制点在二维平面上移动的方向（搜索方向），可设定方向下标按顺时针（上、右、下、左）递增。此时对于方向下标 i，其反方向下标为 i ^ 2（对2做按位异或运算），也可手动if设置求得。

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};	// 上(-1, 0)，右(0, 1)，下(1, 0)，左(0, -1)

  • 1

1 树与图的存储

一般的树均可用图的方式来存储，无向图相当于弧均双向的特殊的有向图。

二叉树可用二叉链表存储。

1.1 邻接矩阵

注意无法存储重边，因此通常选择存储所有重边权中的最值。适合存稠密图，可随机存取任意边。

int g[N][N];	// g[a][b]存储有向边<a, b>

/* 初始化 */
memset(g, 0x3f, sizeof g);

  • 1
  • 2
  • 3
  • 4

1.2 邻接表

相当于同时开 n n n 条无头单链表，表h[k]存储点 k k k 的所有出边。适合存稀疏图，可快速遍历某点的所有出边。

const int N = 1e5, M = 2 * N;
  
int n, m;	// 点数、边数
int h[N], e[M], ne[M], idx;		// h[k]为点k的边表的头指针

/* 初始化 */
memset(h, -1, sizeof h);
idx = 0;

/* 添加一条边<a, b> */
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

2 树与图的遍历

时间复杂度： O ( n + m ) O(n+m) O(n+m)

2.1 深度优先遍历(DFS)

bool st[N];

int dfs(int u) {
    st[u] = true;
  
    for (int i = h[u]; ~i; i = ne[i]) {	// 遍历u的所有出边
        int v = e[i];
        if (!st[v]) dfs(v);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

2.2 宽度优先遍历(BFS)

bool st[N];		// V: [1 ... n]

void bfs() {
    queue<int> q;
    q.push(1);		// 队中压入源点
    st[1] = true;

    while (!q.empty()) {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i]) {	// 遍历点t的所有出边
            int u = e[i];
            if (!st[u]) {
                st[u] = true;
                q.push(u);
            }
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

3 拓扑排序

时间复杂度： O ( n + m ) O(n+m) O(n+m)

int n;		// V: [1 ... n]
int q[N], hh = 0, tt = -1;	// 顶点队列，存储拓扑序列
int d[N];	// d[i]存储点i的入度

/* 拓扑排序：将拓扑序列存在队列中 */
bool topsort() {
    for (int i = 1; i <= n; i++)	// 将所有度为0的点入队
        if (d[i] == 0) q[++tt] = i;
  
    while (hh <= tt) {
        int t = q[hh++];
  
        for (int i = h[t]; ~i; i = ne[i]) {	// 遍历点t的所有出边
            int u = e[i];	// 该出边对应的点u
            if (--d[u] == 0) q[++tt] = u;	// 删去该出边并判定：u入度变为0了则入队
        }
    }
  
    return tt = n - 1;	// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列
}

/* 输出拓扑序列（若存在） */
if (topsort()) {
    for (int i = 0; i < n; i++) printf("%d ", q[i]);
    puts("");
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

4 最短路径

4.1 朴素Dijkstra算法

时间复杂度： O ( n 2 + m ) O(n^2+m) O(n2+m)

适用情形：稠密图

int n;			// V: [1 ... n]
int g[N][N];	// 邻接矩阵图（带权）
int dist[N];	// dist[]存储起点到每个点的最短路径
bool st[N];		// st[]标记每个点的最短路是否已被确定

/* 求起点S到终点T的最短路，若不存在则返回-1 */
int dijkstra(int S, int T) {
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;	// 这里只先设起点的dist
  
    for (int i = 0; i < n; i++) {	// 迭代n次（第1轮预处理起点）
        int t = -1;	// 在还未确定最短路的点中，寻找最短距离点t
        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++)	// 用t更新其他点的距离
            if (dist[j] > dist[t] + g[t][j])
                dist[j] = dist[t] + g[t][j];
    }
  
    if (dist[T] == 0x3f3f3f3f) return -1;
    return dist[T];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

4.2 堆优化Dijkstra算法

时间复杂度： O ( m log ⁡ n ) O(m\log n) O(mlogn)

适用情形：稀疏图

typedef pair<int, int> PII;

int n;			// V: [1 ... n]
int h[N], e[M], w[M], ne[M], idx;	// 邻接表图，w[i]存边i的权值
int dist[N];	// dist[]存储起点到每个点的最短路径
bool st[N];		// st[]标记每个点的最短路是否已被确定

/* 求起点S到终点T的最短路，若不存在则返回-1 */
int dijkstra(int S, int T) {
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;	// 这里也只先设起点的dist
  
    priority_queue<PII, vector<PII>, greater<PII> > heap;	// 小根堆
    heap.push({0, S});		// (distance, vertex)
  
    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();
        int u = t.second, distance = t.first;	// 用堆得到最近的点及与其距离
  
        if (st[u]) continue;	// 若已确定则跳过
        st[u] = true;
  
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (dist[v] > distance + w[i]) {
                dist[v] = distance + w[i];
                heap.push({dist[v], v});
            }
        }
    }
  
    if (dist[T] == 0x3f3f3f3f) return -1;
    return dist[T];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

4.3 Bellman-Ford算法

时间复杂度： O ( n m ) O(nm) O(nm)

适用情形：存在负权边的图

int n, m;		// V: [1 ... n]
struct Edge {
    int a, b, w;
} edges[M];		// 边集，存储权值为w的有向边<a, b>
int dist[N];	// dist[]存储起点到每个点的最短路径

/* 求起点S到终点T的最短路，若不存在则返回-1 */
int bellman_ford(int S, int T) {
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
  
    for (int i = 0; i < n; i++) {	// 要求最大长度为n的最短路径，故迭代n次
        for (int j = 0; j < m; j++) {	// 每次遍历全部m条边
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)	// 松弛操作：更新当前dist
                dist[b] = dist[a] + w;
        }
    }
  
    if (dist[T] > 0x3f3f3f3f / 2) return 0x3f3f3f3f;	// 因为负权边的存在，可能略低于INF
    return dist[T];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

应用：求有边数限制的最短路

限制 k k k 条边就进行 k k k 轮迭代遍历，遍历开始前需先备份 dist[]于 backup[]，用其将 dist[]更新。

int n, m, k;	// 限制最短路最多经过k条边
struct Edge {
    int a, b, w;
} edges[M];
int dist[N], backup[N];	// backup[]备份dist[]数组，防止发生串联（用改后数据去改别人）

/* 求起点S到终点T的最短路，若不存在则返回-1 */
int bellman_ford(int S, int T) {
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
  
    for (int i = 0; i < k; i++) {	// 限制k条边，则迭代k次
        memcpy(backup, dist, sizeof dist);	// 遍历边前先将dist拷贝至备份数组
        for (int j = 0; j < m; j++) {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > backup[a] + w)	// 使用备份数组做松弛操作
                dist[b] = backup[a] + w;
        }
    }
  
    if (dist[T] > 0x3f3f3f3f / 2) return 0x3f3f3f3f;
    return dist[T];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

4.4 SPFA算法

时间复杂度：平均 O ( m ) O(m) O(m) ，最坏 O ( n m ) O(nm) O(nm)

队列优化的Bellman-Ford算法，后继变小了当前dist才变小。

int n;			// V: [1 ... n]
int h[N], e[M], w[M], ne[M], idx;	// 邻接表图，w[i]存边i的权值
int dist[N];	// dist[]存储起点到每个点的最短路径
bool st[N];		// st[]标记每个点的最短路是否已被确定

int spfa(int S, int T) {
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
  
    queue<int> q;	// 队中存放待更新的点（用堆也行）
    q.push(S);
    st[S] = true;	// 结点入队时做标记
  
    while (!q.empty()) {	// 使用BFS的思想
        auto t = q.front();
        q.pop();
  
        st[t] = false;	// 结点出队时撤销标记（之后可能需再次入队被更新）
  
        for (int i = h[t]; ~i; i = ne[i]) {
            int u = e[i];
            if (dist[u] > dist[t] + w[i]) {
                dist[u] = dist[t] + w[i];
                if (!st[u]) {	// 若更新了u的距离，则其出边所指也可能待更新，判断将其入队
                    q.push(u);
                    st[u] = true;
                }
            }
        }
    }
  
    if (dist[T] == 0x3f3f3f3f) return 0x3f3f3f3f;
    return dist[T];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

应用：判断图中是否存在负环

时间复杂度： O ( n m ) O(nm) O(nm)

不需要初始化 dist[]，因此之后正权入边顶点永不会被更新。并且为了消除某点可能无法到达负环的影响，将所有点全入队并标记！

原理：若某条最短路径上有 n n n 个点（除了自己），则加上自己之后一共有 n + 1 n+1 n+1 个点，由抽屉原理一定有两个点相同，所以存在负环。

int n;
int h[N], e[M], w[M], ne[M], idx;]
int dist[N], cnt[N];	// cnt[x]存储起点（任意）到x的最短路中经过的点数
bool st[N];

/* 如果存在负环，则返回true，否则返回false */
bool spfa() {
    queue<int> q;	// 不需要初始化dist数组，直接将所有点全入队并标记！
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
    }
  
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
  
        st[t] = false;
  
        for (int i = h[t]; ~i; i = ne[i]) {
            int u = e[i];
            if (dist[u] > dist[t] + w[i]) {
                dist[u] = dist[t] + w[i];
                cnt[u] = cnt[t] + 1;	// 若更新了u的距离，则立即更新其cnt（前驱加1）
                if (cnt[u] >= n) return true;	// 若最短路已包含至少n个点（不含自身），则有负环
                if (!st[u]) {
                    q.push(u);
                    st[u] = true;
                }
            }
        }
    }
  
    return false;	// 跳出循环则说明无负环
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

4.5 Floyd算法

时间复杂度： O ( n 3 ) O(n^3) O(n3)

基于动态规划

int n, m;		// V: [1 ... n]
int dist[N][N];	// 邻接矩阵图，经过Floyd()操作后变为存储最短距离

/* 初始化 */
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (i == j) dist[i][j] = 0;
		else dist[i][j] = 0x3f3f3f3f;
// 之后被更新为边权

/* 算法结束后，d[a][b]表示a到b的最短距离 */
void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

5 最小生成树

5.1 朴素版Prim算法

时间复杂度： O ( n 2 + m ) O(n^2+m) O(n2+m)

必须先累加 res再更新 dist[]，以避免负自环污染当前 t最短距离

const int INF = 0x3f3f3f3f;

int n;			// V: [1 ... n]
int g[N][N];	// 邻接矩阵图
int dist[N];	// dist[]存储起点到当前最小生成树(MST)的最短距离
bool st[N];		// st[]标记每个点是否已经在生成树中

/* 若图不连通，则返回INF，否则返回最小生成树的最小代价 */
int prim() {
    memset(dist, 0x3f, sizeof dist);	// 仅计算最小代价，故无需另设起点，不应先置标记为true
  
    int res = 0;	// 存储最小代价
    for (int i = 0; i < n; i++) {	// 迭代n次（第1轮预处理生成树根）
        int t = -1;	// 在还未并入MST的点中，寻找最短距离点t
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
  
        if (i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;	// 从第2轮起，若最短距离为无穷，则说明不连通
        if (i) res += dist[t];	// 从第2轮起，将t的距离计入最小代价（须先累加res）
        st[t] = true;	// 将t并入MST
  
        for (int j = 1; j <= n; j++)	// 用新并入的t更新各点到生成树的距离
            if (dist[j] > g[t][j]) 	// 与dij不同，不应加前驱的dist（求取到整棵树的距离）
                dist[j] = g[t][j];
    }
  
    return res;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

5.2 Kruskal算法

时间复杂度： O ( m log ⁡ m ) O(m\log m) O(mlogm)

int n, m;		// V: [1 ... n]
struct Edge {
    int a, b, w;
  
    bool operator<(const Edge &t) const {	// 重载运算符，用于按权递增排序
        return w < t.w;
    }
} edges[MAXM];	// 边集，存储权值为w的有向边<a, b>
int p[N];		// 并查集

/* 并查集核心操作 */
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

/* 若图不连通，则返回INF，否则返回最小生成树的最小代价 */
int kruskal() {
    sort(edges, edges + m);	// 将边按权递增排序（方式不限）
  
    for (int i = 1; i <= n; i++) p[i] = i;	// 初始化并查集
  
    int res = 0, cnt = 0;
    for (int i = 0; i < m; i++) {	// 枚举所有边，将合适的边并入MST（加入集合）
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
  
        if (find(a) != find(b)) {	// 如果两个连通块不连通，则将这两个连通块合并
            p[find(a)] = find(b);
            res += w;
            cnt++;
        }
    }
  
    if (cnt < n - 1) return 0x3f3f3f3f;	// 判定连通性（连通的必要条件：|E| = |V| - 1）
    return res;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

6 二分图

在这里插入图片描述

定义：二分图可将图中顶点划分两个集合，使得集合内顶点互不邻接，不同集合顶点可邻接

定理：图为二分图 ⇔ \Leftrightarrow ⇔ 图中不含奇数环

6.1 染色法

时间复杂度： O ( n + m ) O(n+m) O(n+m)

判断是否是二分图

思想：若为二分图，则与黑点相连的点均为白色，与白点相连的点均为黑色（邻接顶点不得同色）

int n;			// V: [1 ... n]
int h[N], e[M], ne[M], idx;	// 邻接表图
int color[N];	// 每个点的颜色：-1未染色，0白色，1黑色

/* 用dfs给结点u染颜色c，一切顺利返回true，出现冲突则返回false */
bool dfs(int u, int c) {
    color[u] = c;	// 给结点u染颜色c
  
    for (int i = h[u]; ~i; i = ne[i]) {	// 遍历所有从结点u指出的点
        int v = e[i];
        if (color[v] == -1) {	// 若v未染色则将其染与u相反的色(!c)并判定是否冲突
            if (!dfs(v, !c)) return false;
        } else if (color[v] == c) return false;	// 若v与u同色则出现冲突
    }
  
    return true;
}

/* 用染色法判断图是否是二分图 */
memset(color, -1, sizeof color);
bool success = true;
for (int i = 1; i <= n; i++)	// 遍历所有顶点，若未染色则染白色并判定是否冲突
    if (color[i] == -1)
        if (!dfs(i, 0)) {
            success = false;
            break;
        }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

6.2 匈牙利算法

时间复杂度：最差 O ( n m ) O(nm) O(nm) ，实际运行时间一般远小于 O ( n m ) O(nm) O(nm)

用于求二分图的最大匹配数（匹配：某两个点有且只有他们之间有边，与别人无边）

匈牙利算法中只会用到从第1个集合指向第2个集合的边，所以这里只用存一个方向的边。

先欣赏y神讲解再看代码

int n1, n2;		// 二分图中两个集合的点数。集合1: [1 ... n1]、集合2: [1 ... n2]
int h[N], e[M], ne[M], idx;	// 邻接表图，只存集合1到集合2的边
int match[N];	// match[i] = j表示集合2的点i当前匹配集合1的点j（j=0表示暂无匹配）
bool st[N];		// st[i]标记集合2的点i是否已经被遍历过

/* 寻找与集合1的点u匹配集合2的点，返回是否成功 */
bool find(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {	// "遍历所有可能的她"
        int v = e[i];
        if (!st[v]) {
            st[v] = true;
            if (match[v] == 0 || find(match[v])) {	// 判定"若她有则'去找他'"
                match[v] = u;	// 与她匹配
                return true;
            }
        }
    }
  
    return false;
}

/* 求最大匹配数 */
int res = 0;
for (int i = 1; i <= n1; i++) {	// 依次枚举集合1的每个点去匹配集合2的点
    memset(st, false, sizeof st);	// 每次重置遍历标记
    if (find(i)) res++;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/600857
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号