今日计划

  • 完成阅读《图解TCP/IP》的第二章，尽可能的完成笔记
  • 学习图论最短路算法
  • 推进项目

算法小计

存储图的三种方式

设 m = 边的数量，n = 点的数量

邻接矩阵 ： 适用于 边的数量接近点的数量的平方的情况 $m \approx n^2$ 

// 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
int[][] w = new int[N][N];

// 加边操作
void add(int a, int b, int c) {
    w[a][b] = c;
}

邻接表：适用于 边的数量接近点的数量的情况 $m \approx n$ 

int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
int idx;

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

首先 idx 是用来对边进行编号的，然后对存图用到的几个数组作简单解释：

  • he 数组：存储是某个节点所对应的边的集合（链表）的头结点；
  • e 数组：由于访问某一条边指向的节点；
  • ne 数组：由于是以链表的形式进行存边，该数组就是用于找到下一条边；
  • w 数组：用于记录某条边的权重为多少。

因此当我们想要遍历所有由 a 点发出的边时，可以使用如下方式：

for (int i = he[a]; i != -1; i = ne[i]) {
    int b = e[i], c = w[i]; // 存在由 a 指向 b 的边，权重为 c
}

类

这是一种最简单，但是相比上述两种存图方式，使用得较少的存图方式。

只有当我们需要确保某个操作复杂度严格为$O(m)$时，才会考虑使用

具体的，我们建立一个类来记录有向边信息：

class Edge {
    // 代表从 a 到 b 有一条权重为 c 的边
    int a, b, c;
    Edge(int _a, int _b, int _c) {
        a = _a; b = _b; c = _c;
    }
}

通常我们会使用 List 存起所有的边对象，并在需要遍历所有边的时候，进行遍历：

List<Edge> es = new ArrayList<>();

...

for (Edge e : es) {
    ...
}

743. 网络延迟时间 - 力扣（LeetCode）

分析：约定边的数量为 m 点的数量 为 n

查看数据范围，n的范围是100，m的范围是6000，使用邻接表 或者 邻接矩阵都可以

本题要求的是 从 k 点出发，所有点都被访问到的最短时间，问题转换一下就是 求从 k 点出发，到其他点x的最短距离的最大值

第一种最短路：

Floyd (邻接矩阵) 时间复杂度 $O(n^3)$

第一遍 Floyd，可以得到从任意起点出发，到达任意点的最短距离

然后从所有 $w[k][x]$​中取出最大值

class Solution {
    int N = 110, M = 6010;
    // 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
    int[][] w = new int[N][N];
    int INF = 0x3f3f3f3f;
    int n, k;
    public int networkDelayTime(int[][] ts, int _n, int _k) {
        n = _n; k = _k;
        // 初始化邻接矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                w[i][j] = w[j][i] = i == j ? 0 : INF;
            }
        }
        // 存图
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            w[u][v] = c;
        }
        // 最短路
        floyd();
        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, w[k][i]);
        }
        return ans >= INF / 2 ? -1 : ans;
    }
    void floyd() {
        // floyd 基本流程为三层循环：
        // 枚举中转点 - 枚举起点 - 枚举终点 - 松弛操作        
        for (int p = 1; p <= n; p++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    w[i][j] = Math.min(w[i][j], w[i][p] + w[p][j]);
                }
            }
        }
    }
}