存图方式

存图方式

邻接矩阵

这是一种使用二维矩阵来进行存图的方式。

适用于边数较多的稠密图使用，当边数量接近点的数量的平方时，可定义为稠密图。

// 邻接矩阵数组：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;
}

邻接表

这也是一种在图论中十分常见的存图方式，与数组存储单链表的实现一致（头插法）。这种存图方式又叫链式前向星存图。

适用于边数较少的稀疏图使用，当边数量接近点的数量，可定义为稀疏图。

// N 为节点数，M 为边数
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;
    // 头插法！遍历到he[a] = -1代表结束
    ne[idx] = he[a];
    he[a] = idx;

    w[idx] = c;
    idx++;
}

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

1. he 数组：存储是某个节点所对应的边的集合（链表）的头结点；
2. e 数组：存储访问某一条边指向的节点；
3. ne 数组：由于是以链表的形式进行存边，该数组就是用于找到下一条边；
4. 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) {
    ...
}

参考：https://leetcode-cn.com/problems/network-delay-time/solution/gong-shui-san-xie-yi-ti-wu-jie-wu-chong-oghpz/

743. 网络延迟时间

Floyd（邻接矩阵）

跑一遍 Floyd，可以得到「从任意起点出发，到达任意起点的最短距离」。然后从所有 w[k][x]中取 max 即是「从 k 点出发，到其他点 x 的最短距离的最大值」。

class Solution {
    int[][] w;
    int INF = 0x3f3f3f3f;
    int N;
    public int networkDelayTime(int[][] times, int n, int k) {
        N = n;
        w = new int[N + 1][N + 1];
        // 初始化邻接矩阵
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                w[i][j] = i == j ? 0 : INF;
            }
        }
        // 存图
        for(int[] t : times){
            w[t[0]][t[1]] = t[2];
        }
        floyd();
        int ret = 0;
        for(int i = 1; i <= N; i++){
            ret = Math.max(ret,w[k][i]);
        }
        return ret > INF / 2 ? -1 : ret;
    }
    private 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]);
                }
            }
        }
    }
}

dijkstra（邻接矩阵）

同理，我们可以使用复杂度为 O（n^2） 的「单源最短路」算法朴素 Dijkstra 算法进行求解，同时使用「邻接矩阵」来进行存图。

class Solution {
    // 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
    int[][] w;
    int N, K;
    int INF = 0x3f3f3f3f;
    // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
    int[] dist;
    // 记录哪些点已经被更新过
    boolean[] visited;
    public int networkDelayTime(int[][] times, int n, int k) {
        N = n;
        K = k;
        w = new int[N + 1][N + 1];
        dist = new int[N + 1];
        visited = new boolean[N + 1];
        // 初始化邻接矩阵
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++)w[i][j] = i == j ? 0 : INF;
        }
        // 存图
        for(int[] t : times)w[t[0]][t[1]] = t[2];
        dijkstra();
        int ret = 0;
        // 注意这里不能用增强for循环，因为dist[0] = INF
        for(int i = 1; i <= N; i++)ret = Math.max(ret,dist[i]);
        return ret > INF / 2 ? -1 : ret;
    }
    private void dijkstra(){
        // 起始先将所有的点标记为「未更新」和「距离为正无穷」
        Arrays.fill(dist,INF);
        Arrays.fill(visited,false);
        // 只有起点最短距离为 0
        dist[K] = 0;
        // 迭代 n 次，这里p没有意义
        for(int p = 1; p <= N; p++){
            int t = -1;
            // 每次找到「最短距离最小」且「未被更新」的点 t
            for(int i = 1; i <= N; i++){
                if(!visited[i] && (t == -1 || dist[i] < dist[t]))t = i;
            }
            // 标记点 t 为已更新
            visited[t] = true;
            // 用点 t 的「最小距离」更新其他点
            for(int i = 1; i <= N; i++){
                dist[i] = Math.min(dist[i],dist[t] + w[t][i]);
            }
        }
    }
}

dijkstra（邻接表）

由于边数据范围不算大，我们还可以使用复杂度为 O（m logn） 的堆优化 Dijkstra 算法进行求解。

class Solution {
    int N = 110,M = 6010,K;
    int[] he = new int[N],e = new int[M],ne = new int[M],w = new int[M];
    int idx;
    int[] dist = new int[N];
    boolean[] visited = new boolean[N];
    int INF = 0x3f3f3f3f;
    private void add(int a, int b, int c){
        e[idx] = b;
        // 头插法
        ne[idx] = he[a];
        he[a] = idx;
        w[idx] = c;
        idx++;
    }
    public int networkDelayTime(int[][] times, int n, int k) {
        K = k;
        // 初始化链表头
        Arrays.fill(he,-1);
        // 存图
        for(int[] t : times){
            add(t[0],t[1],t[2]);
        }
        dijkstra();
        int ret = 0;
        for(int i = 1; i <= n; i++)ret = Math.max(ret,dist[i]);
        return ret > INF / 2 ? -1 : ret;
    }
    private void dijkstra(){
        Arrays.fill(dist,INF);
        // 只有起点最短距离为 0
        dist[K] = 0;
        // 使用「优先队列」存储所有可用于更新的点
        // 以 (点编号, 到起点的距离) 进行存储，优先弹出「最短距离」较小的点
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> a[1] - b[1]);
        q.offer(new int[]{K,0});
        while(!q.isEmpty()){
            int[] poll = q.poll();
            int a = poll[0],d = poll[1];
            // 如果弹出的点被标记「已更新」，则跳过
            if(visited[a])continue;
            // 标记该点「已更新」，并使用该点更新其他点的「最短距离」
            visited[a] = true;
            for(int i = he[a]; i != -1; i = ne[i]){
                int b = e[i];
                if(dist[b] > dist[a] + w[i]){
                    dist[b] = dist[a] + w[i];
                    q.offer(new int[]{b,dist[b]});
                }
            }
        }
    }
}