算法备忘录·搜索与图论

本文最后更新于:2021年10月3日 下午

一直以来,没能系统学习算法,是我心中的痛;现在学了y总的算法基础课,做做笔记,希望能够有所收获。
这是第四节,搜索与图论。

搜索与图论

图的搜索

搜索 数据结构 空间 优劣
DFS stack O(h) 不具有最短性
BFS queue O(2^h) “最短路”

DFS

  • 顺序——搜索树
    • 递归(系统帮我们维护了栈)—— 回溯(从递归出来后还原现场)
      • 剪枝:递归过程中能够直接判断然后回溯
  • 一般无通用框架,关键是搜索的顺序

BFS

  • 能够搜索到最短(边的权重为 1)
  • 有通用的框架
    1
    2
    3
    4
    5
    queue ← 初始状态
    while (queue 不空){
    t ← 队头
    扩展队头
    }

图的存储

  • 有向图、无向图(无向图就当作双向有向图)

邻接矩阵

  • g[a][b] 存储边 a->b

邻接表

  • 每个点有一个单链表,类似于拉链法
  • 使用的邻接表的 TLE 极可能是没有初始化 h[]
  • 模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 对每个节点 k,开单链表,存储其能够走到的所有点。h[k] 存储单链表的头节点
    int h[N], e[N], ne[N], idx;

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

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

图的遍历

  • 时间复杂度为 O(n+m)O(n + m)nn 表示点数,mm 表示边数

深度优先遍历

  • 遍历不需要恢复现场
  • 模板
    1
    2
    3
    4
    5
    6
    7
    8
    int dfs(int u){
    st[u] == true; // st[u] 表示点 u 已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i]){
    int j = e[i];
    if (!st[j]) dfs(j); //不需要恢复现场
    }
    }

宽度优先遍历

  • 模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    queue<int> q;

    st[1];
    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 (!st[j]){
    st[j] = true; // 表示点 j 已经被遍历过
    q.push(j);
    }
    }
    }

有向图的拓扑序列

  • 宽度优先搜索的应用
  • 拓扑序列:所有的边都是从前指向后的
    • 有向无环图一定存在拓扑序列——所以有向无环图称为拓扑图
  • 模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    bool tosort(){
    int hh = 0, tt = -1;

    // d[i] 存储点的入度
    for (int i = 1; i <= n; i ++ ){
    if (!d[i])
    q[++ tt] = i; // 加入所有入度为 0 的点
    }

    while (hh <= tt){
    int t = q[hh ++];
    // 对于队头 t,遍历其子节点,将子节点每个入度 - 1,如果入度为 0 则入队。
    for (int i = h[t]; i != -1; i = ne[i]){
    int j = e[i];
    if (--d[j] == 0)
    q[++ tt] = j;
    }
    }

    //如果所有点都入队了,说明存在拓扑序列;
    return tt = n - 1;
    }

最短路

图论最难的部分是实现

  • 图中有 nn 个点、mm 条边
graph LR
    A[最短路] -->B[单源最短路]
    A --> C[多源汇最短路]
    B --> D[所有边权都是正数]
    B --> E[存在负权边]
    D --> F[朴素 Dijstra 算法]
    D --> G[堆优化版的 Dijstra 算法]
    E --> H[Bellman-Ford]
    E --> I[SPFA]
    C --> J[Floyd 算法]

朴素 Dijkstra 算法

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

  • 算法思路

    1. dist[1] = 0, dist[i] = + INF;
    2. for i in 1 ~ n:
      t ← 不在 s 中的、距离最近的点(s 是当前已确定最短距离的点);
      s ← t;
      用 t 更新其它点(1 ~ n)的距离;
    3. 执行 2 操作 n 次
  • 模板

    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
    int g[N][N]; // 存储每条边
    int dist[N]; // 存储 1 号点到每个点的距离
    bool st[N]; // 存储每个点的最短路是否已经确定

    // 求 1 号点到 n 号点的最短路,若不存在则返回 -1
    int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i <n - 1; i ++ ){
    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;

    // 用 t 更新其他点的距离
    for (int j = 1; j <= n; j ++ ){
    dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    }

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

堆优化版 Dijkstra

  • 我们发现,朴素 Dijkstra 每次需要寻找未确定最短路的点中距离最小的点,那么我们可以用小根堆来维护这个最小值点
  • 时间复杂度 O(mlogn)O(mlogn),适合稀疏图
  • 使用邻接表存储,是为了快速找到从每个点出发的所有邻边
  • 模板
    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
    typedef pair<int, int> PII;

    int n; // 点的数量
    int h[N], w[N], e[N], ne[N], idx; // 邻接表存储
    int dist[N]; // 存储 1 号点到每个点的距离
    bool st[N]; // 存储每个点的最短路是否已经确定

    int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1}); // first 存储距离,second 存储节点编号

    // 队列为空时,即没有点更新距离
    while (heap.size()){
    // 相比于朴素版,这里直接取了堆顶
    auto t = heap.top();
    heap.pop();

    int ver = t.second, distance = t.first;

    if (st[ver]) continue;
    st[ver] = true;

    for (int i = h[ver]; i != -1; i = ne[i]){
    int j = e[i];
    if (dist[j] > distance + w[i]){
    dist[j] = distance + w[i];
    heap.push({dist[j], j}); // 将更新了距离的点放入队列
    }
    }
    }
    }

Bellman-Ford 算法

  • 时间复杂度 O(nm)O(nm),其中 nn 表示点数,mm 表示边数
  • 因为有负权边,因此每个点都需要对每个边进行遍历,从而更新 dist[]
  • 如果第 nn 次迭代仍然会松弛三角不等式,就说明存在一条长度是 n+1n+1 的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路
  • 注意最后的 dist[n] > 0x3f3f3f3f / 2
  • 模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    int n, m;
    int dist[N];

    struct Edge{
    int a, b, w;
    }edges[M]; // 边,a表示出点,b表示入点,w表示边的权重

    // 求 1 号点到 n 号点的最短路,若不存在则返回 -1
    int bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n; i ++ ){
    for (int j = 0; j < m; j ++ ){
    int a = edges[j].a, b = edges[j].b, w = edges[j].w;
    dist[b] = min(dist[b], dist[a] + w);
    }
    }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1; // 因为有负权边,所以即便是没有通路 dist[n] 也有可能减少了一些
    return dist[n];

spfa 算法

  • 队列优化的 Bellman-Ford 算法。仅更新队列中的点,这样就加快了速度。但是如果存在闭环,队列会不断更新从而不断循环。
    • 因此,判断负环的方法是引入 cnt[],记录每个点最短距离更新的次数
  • 时间复杂度平均 O(m)O(m),最坏情况下 O(nm)O(nm)。因此时间不是很紧的题可以用 spfa 代替 Dijkstra。
  • 为什么 spfa 最后说可以用 dist[n]==0x3f3f3f3f 进行判断?这是因为,Bellman-ford 在更新时,即便是没有通路从 1 到 n,但是与 n 相连的点 n - 1 也会让 dist[n] 更新;而 spfa 的话,如果没有连接有通路,那么 n - 1 是不会进入队列被更新到。因此 dist[n] 不会变化。
  • 模板
    • spfa 求 1 到 n 的最短路
    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
    int n;  // 总点数
    int h[N], w[N], e[N], ne[N], idx; // 用邻接表存储所有边
    int dist[N]; // 存储 1 号点到每个点的距离
    bool st[N]; // 存储点是否在队列中

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

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size()){
    auto t = q.front();
    q.pop();
    st[t] = false;

    for (int i = h[i]; 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]){ // 如果队列中已存在 j,则不需要将 j 重复插入
    q.push(j);
    st[j] = true;
    }
    }
    }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
    }
    • 判断图中是否存在负环
    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
    int n;
    int h[N], w[N], e[N], ne[N], idx;
    int dist[N], cnt[N];
    bool st[N];

    bool spfa(){
    queue<int> q;

    // 负环不一定要从点 1 出发,因此把所有点放入队列中
    for (int i = 1; i <= n; i ++ ){
    q.push(i);
    st[i] = true;
    }

    while (q.size()){
    auto 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];
    cnt[j] = cnt[t] + 1;
    if (cnt[j] > n) return true; // 说明最短路中至少含了 n + 1 个点
    if (!st[j]){
    q.push(j);
    st[j] = true;
    }
    }
    }
    }
    return false;
    }

FLoyd 算法

  • 时间复杂度是 O(n3)O(n^3)
  • Floyd 算法极其简洁,但是难以理解,因为是用了 DP 思想:核心是公式 f[k][i][j]=min(f[k1][i][j],f[k1][i][k]+f[k1][k][j])f[k][i][j]=min(f[k−1][i][j],f[k−1][i][k]+f[k−1][k][j])。在计算 f[k]f[k] 时,需要依赖于 f[k1]f[k−1],所以 $k4 应该先被算出来。

一个笑话:为什么 Dijkstra 不能提出 floyd 算法?因为他的名字是 ijk 而不是 kij。

  • 模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // 初始化
    for (int i = 1; i <= n; i ++ ){
    for (int j = 1; j <= n; j ++ ){
    if (i == j) d[i][j] = 0;
    else d[i][j] = INF;
    }
    }

    // Floyd 算法结束后,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 ++ ){
    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }
    }
    }
    }

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!