算法备忘录·搜索与图论

本文最后更新于:2021年9月12日 上午

一直以来,没能系统学习算法,是我心中的痛;现在学了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)的距离;
  • 模板
    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}); // 将更新了距离的点放入队列
    }
    }
    }
    }

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