【数据结构与算法】图的模板及例题

2021-08-24

图的存储结构

邻接矩阵

适用于边数较多的情况,采用二维数组存储

// 邻接矩阵数组:w[from][to] = weight 代表从 from 到 to 有权重为 weight 的边
int[][] w = new int[N][N];

// 加边操作
void add(int from, int to, int weight) {
    w[from][to] = weight;
}

邻接表(链式前向星存图)

数组加单链表(头插法)

适用于边数较少的情况

数组模拟链表

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 数组:用于记录某条边的权重为多少。

封装边信息

class Edge {
    // 代表从 a 到 b 有一条权重为 c 的边
    int from, to, weight;
    Edge(int _from, int _to, int _weight) {
        from = _from; to = _to; weight = _weight;
    }
}

并查集

并查集模板

用来判断元素所属问题,是否属于同一个集合。

// UnionFind.class
public class UnionFind {
    int root[];
    // 添加了 rank 数组来记录每个顶点的高度,也就是每个顶点的「秩」
    int rank[];

    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i; //每个元素所在集合的代表元素就是自己
            rank[i] = 1; // 一开始每个顶点的初始「秩」为1,因为它们只有自己本身的一个顶点。
        }
    }

		// 此处的 find 函数实现了路径压缩,返回集合代表元素
    public int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }

		// 按秩合并优化的 union 函数,高度低的集合连在高度高的集合代表元素下面
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX] += 1;
            }
        }
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

}

例题

LeetCode 547. 省份数量

有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

 

示例 1:


输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出:2
示例 2:


输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出:3
 

提示:

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
	class Solution {
            public int findCircleNum(int[][] isConnected) {
                UnionFind uf = new UnionFind(isConnected.length);
                for (int i = 0; i < isConnected.length; i++) {
                    for (int j = i; j < isConnected.length; j++) {
                        if (isConnected[i][j] == 1)
                            uf.union(i, j);
                    }
                }
                int ans = 0;
                for (int i = 0; i < uf.root.length; i++) {
                    if (i == uf.root[i]) ans++;
                }
                return ans;
            }

        }
        class UnionFind {
            public int root[];
            public int rank[];

            public UnionFind(int size) {
                root = new int[size];
                rank = new int[size];
                for (int i = 0; i < size; i++) {
                    root[i] = i;
                    rank[i] = 1;
                }
            }

            public int find(int x) {
                if (x == root[x]) return x;
                return root[x] = find(root[x]);
            }

            public void union(int x, int y) {
                int rootX = find(x);
                int rootY = find(y);
                if (rank[rootX] < rank[rootY]) {
                    root[rootX] = rootY;
                } else if (rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                } else {
                    root[rootY] = rootX;
                    rank[rootX]++;
                }
            }

            public boolean connected(int x, int y) {
                return find(x) == find(y);
            }
        }

单源点最短路

例题

LeetCode 743. 网络延迟时间

有 n 个网络节点,标记为 1 到 n。

给你一个列表 times,表示信号经过 有向 边的传递时间。 
times[i] = (ui, vi, wi),其中 ui 是源节点,vi 是目标节点, wi 是一个信号从源节点传递到目标节点的时间。

现在,从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号?
如果不能使所有节点收到信号,返回 -1 。



示例 1:

输入:times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出:2
示例 2:

输入:times = [[1,2,1]], n = 2, k = 1
输出:1
示例 3:

输入:times = [[1,2,1]], n = 2, k = 2
输出:-1
 

提示:

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都 互不相同(即,不含重复边)

朴素Dijkstra(邻接矩阵)

class Solution {
    int N = 110, M = 6010;
    // 邻接矩阵数组:w[a][b] = c 代表从 a 到 b 有权重为 c 的边
    int[][] w = new int[N][N];
    // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
    int[] dist = new int[N];
    // 记录哪些点已经被更新过
    boolean[] vis = new boolean[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;
        }
        // 最短路
        dijkstra();
        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void dijkstra() {
        // 起始先将所有的点标记为「未更新」和「距离为正无穷」
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        // 只有起点最短距离为 0
        dist[k] = 0;
        // 迭代 n 次
        for (int p = 1; p <= n; p++) {
            // 每次找到「最短距离最小」且「未被更新」的点 t
            int t = -1;
            for (int i = 1; i <= n; i++) {
                if (!vis[i] && (t == -1 || dist[i] < dist[t])) t = i;
            }
            // 标记点 t 为已更新
            vis[t] = true;
            // 用点 t 的「最小距离」更新其他点
            for (int i = 1; i <= n; i++) {
                dist[i] = Math.min(dist[i], dist[t] + w[t][i]);
            }
        }
    }
}

堆优化Dijkstra(邻接表)

class Solution {
    int N = 110, M = 6010;
    // 邻接表
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
    int[] dist = new int[N];
    // 记录哪些点已经被更新过
    boolean[] vis = new boolean[N];
    int n, k, idx;
    int INF = 0x3f3f3f3f;
    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[][] ts, int _n, int _k) {
        n = _n; k = _k;
        // 初始化链表头
        Arrays.fill(he, -1);
        // 存图
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            add(u, v, c);
        }
        // 最短路
        dijkstra();
        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void dijkstra() {
        // 起始先将所有的点标记为「未更新」和「距离为正无穷」
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        // 只有起点最短距离为 0
        dist[k] = 0;
        // 使用「优先队列」存储所有可用于更新的点
        // 以 (点编号, 到起点的距离) 进行存储,优先弹出「最短距离」较小的点
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1]-b[1]);
        q.add(new int[]{k, 0});
        while (!q.isEmpty()) {
            // 每次从「优先队列」中弹出
            int[] poll = q.poll();
            int id = poll[0], step = poll[1];
            // 如果弹出的点被标记「已更新」,则跳过
            if (vis[id]) continue;
            // 标记该点「已更新」,并使用该点更新其他点的「最短距离」
            vis[id] = true;
            for (int i = he[id]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[id] + w[i]) {
                    dist[j] = dist[id] + w[i];
                    q.add(new int[]{j, dist[j]});
                }
            }
        }
    }
}

堆优化 Dijkstra(邻接矩阵)

class Solution {
    int INF = 0x3f3f3f3f;
    int N = 110;
    int M = 6010;
    int[][] w = new int[N][N];
    int n, k;
    boolean[] vis = new boolean[N];
    int[] dis = new int[N];

    public int networkDelayTime(int[][] times, 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[] time : times) {
            w[time[0]][time[1]] = time[2];
        }
        dijkstra();
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dis[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }

    public void dijkstra() {
        Arrays.fill(vis, false);
        Arrays.fill(dis, INF);
        dis[k] = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        q.add(new int[]{k, 0});
        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int id = poll[0];
            int weight = poll[1];
            if (!vis[id]) {
                vis[id] = true;
                for (int i = 1; i <= n; i++) {
                    if (dis[i] > dis[id] + w[id][i]) {
                        dis[i] = dis[id] + w[id][i];
                        q.add(new int[]{i, dis[i]});
                    }

                }
            }
        }
    }
}

Bellman Ford 算法

可以解决有负权图问题

封装边

class Solution {
    class Edge {
        int a, b, c;
        Edge(int _a, int _b, int _c) {
            a = _a; b = _b; c = _c;
        }
    }
    int N = 110, M = 6010;
    // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
    int[] dist = new int[N];
    int INF = 0x3f3f3f3f;
    int n, m, k;
    // 使用类进行存边
    List<Edge> es = new ArrayList<>();
    public int networkDelayTime(int[][] ts, int _n, int _k) {
        n = _n; k = _k;
        m = ts.length;
        // 存图
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            es.add(new Edge(u, v, c));
        }
        // 最短路
        bf();
        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void bf() {
        // 起始先将所有的点标记为「距离为正无穷」
        Arrays.fill(dist, INF);
        // 只有起点最短距离为 0
        dist[k] = 0;
        // 迭代 n 次
        for (int p = 1; p <= n; p++) {
            int[] prev = dist.clone();
            // 每次都使用上一次迭代的结果,执行松弛操作
            for (Edge e : es) {
                int a = e.a, b = e.b, c = e.c;
                dist[b] = Math.min(dist[b], prev[a] + c);
            }
        }
    }
}

邻接表

class Solution {
    int N = 110, M = 6010;
    // 邻接表
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
    int[] dist = new int[N];
    int INF = 0x3f3f3f3f;
    int n, m, k, idx;
    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[][] ts, int _n, int _k) {
        n = _n; k = _k;
        m = ts.length;
        // 初始化链表头
        Arrays.fill(he, -1);
        // 存图
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            add(u, v, c);
        }
        // 最短路
        bf();
        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void bf() {
        // 起始先将所有的点标记为「距离为正无穷」
        Arrays.fill(dist, INF);
        // 只有起点最短距离为 0
        dist[k] = 0;
        // 迭代 n 次
        for (int p = 1; p <= n; p++) {
            int[] prev = dist.clone();
            // 每次都使用上一次迭代的结果,执行松弛操作
            for (int a = 1; a <= n; a++) {
                for (int i = he[a]; i != -1; i = ne[i]) {
                    int b = e[i];
                    dist[b] = Math.min(dist[b], prev[a] + w[i]);
                }
            }
        }
    }
}

SPFA 算法

SPFA 是 Shortest Path Faster Algorithm 的简写。

它是对Bellman Ford 算法的优化。

class Solution {
    int N = 110, M = 6010;
    // 邻接表
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
    int[] dist = new int[N];
    // 记录哪一个点「已在队列」中
    boolean[] vis = new boolean[N];
    int INF = 0x3f3f3f3f;
    int n, k, idx;
    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[][] ts, int _n, int _k) {
        n = _n; k = _k;
        // 初始化链表头
        Arrays.fill(he, -1);
        // 存图
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            add(u, v, c);
        }
        // 最短路
        spfa();
        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void spfa() {
        // 起始先将所有的点标记为「未入队」和「距离为正无穷」
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        // 只有起点最短距离为 0
        dist[k] = 0;
        // 使用「双端队列」存储,存储的是点编号
        Deque<Integer> d = new ArrayDeque<>();
        // 将「源点/起点」进行入队,并标记「已入队」
        d.addLast(k);
        vis[k] = true;
        while (!d.isEmpty()) {
            // 每次从「双端队列」中取出,并标记「未入队」
            int poll = d.pollFirst();
            vis[poll] = false;
            // 尝试使用该点,更新其他点的最短距离
            // 如果更新的点,本身「未入队」则加入队列中,并标记「已入队」
            for (int i = he[poll]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[poll] + w[i]) {
                    dist[j] = dist[poll] + w[i];
                    if (vis[j]) continue;
                    d.addLast(j);
                    vis[j] = true;
                }
            }
        }
    }
}

最小生成树

例题

LeetCode 1584. 连接所有点的最小费用

给你一个points 数组,表示 2D 平面上的一些点,其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 :|xi - xj| + |yi - yj| ,其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时,才认为所有点都已连接。

 

示例 1:



输入:points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出:20
解释:

我们可以按照上图所示连接所有点得到最小总费用,总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。
示例 2:

输入:points = [[3,12],[-2,5],[-4,1]]
输出:18
示例 3:

输入:points = [[0,0],[1,1],[1,0],[-1,1]]
输出:4
示例 4:

输入:points = [[-1000000,-1000000],[1000000,1000000]]
输出:4000000
示例 5:

输入:points = [[0,0]]
输出:0
 

提示:

1 <= points.length <= 1000
-106 <= xi, yi <= 106
所有点 (xi, yi) 两两不同。

Kruskal 算法

在「Kruskal 算法」中,我们通过增加边数来扩大「最小生成树」;

class Solution {
    public int minCostConnectPoints(int[][] points) {
        PriorityQueue<Edge> queue = new PriorityQueue<>((e1, e2)->e1.weight-e2.weight);
        for (int i = 0; i < points.length - 1; i++) {
            for (int j = i + 1; j < points.length; j++) {
                int x1 = points[i][0];
                int y1 = points[i][1];
                int x2 = points[j][0];
                int y2 = points[j][1];
                int cost = Math.abs(x1 - x2) + Math.abs(y1 - y2);
                Edge edge = new Edge(i, j, cost);
                queue.add(edge);
            }
        }
        UnionFind uf = new UnionFind(points.length);
        int ans = 0;
        int count = points.length - 1;  //若n个点,则 count=n-1(树的定义)
        while (!queue.isEmpty() && count > 0) {
            Edge edge = queue.poll();
            if (!uf.connected(edge.point1, edge.point2)) {
                uf.union(edge.point1, edge.point2);
                ans += edge.weight;
                count--;
            }
        }
        return ans;
    }
}


class Edge {
    public int point1;
    public int point2;
    public int weight;

    public Edge(int p1, int p2, int w) {
        point1 = p1;
        point2 = p2;
        weight = w;
    }
}

class UnionFind {
    int root[];
    int rank[];

    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (x == root[x]) return x;
        return root[x] = find(root[x]);
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rank[rootX] < rank[rootY]) {
            root[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            root[rootY] = rootX;
        } else {
            root[rootY] = rootX;
            rank[rootX]++;
        }
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

Prim 算法

在「Prim 算法」中,我们通过增加顶点来扩大「最小生成树」。

class Solution {

    public int minCostConnectPoints(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        int size = points.length;
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>((x, y) -> x.cost - y.cost);
        boolean[] visited = new boolean[size];
        int result = 0;
        int count = size - 1;
        // 计算以0为起点的所有边的值
        for (int j = 1; j < size; j++) {
            
            int[] coordinate1 = points[0];
            int[] coordinate2 = points[j];
            int cost = Math.abs(coordinate1[0] - coordinate2[0]) + Math.abs(coordinate1[1] - coordinate2[1]);
            Edge edge = new Edge(0, j, cost);
            pq.add(edge);
        }
        visited[0] = true;

        while (pq.size() > 0 && count > 0) {
            Edge e = pq.poll();
            int point1 = e.point1;
            int point2 = e.point2;
            int cost = e.cost;
            if ( !visited[point2] ) {
                result += cost;
                visited[point2] = true;
                for (int j = 0; j < size; j++ ) {
                    if ( !visited[j] ) {
                        int distance = Math.abs(points[point2][0] - points[j][0]) + Math.abs(points[point2][1] - points[j][1]);
                        pq.add(new Edge(point2, j, distance));
                    }
                }
                count--;
            }
        }
        return result;
    }

    class Edge {
        int point1;
        int point2;
        int cost;

        Edge(int point1, int point2, int cost) {
            this.point1 = point1;
            this.point2 = point2;
            this.cost = cost;
        }
    }
}

拓扑排序

例题

LeetCode 210.课程表 II

现在你总共有 n 门课需要选,记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件,返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序,你只要返回一种就可以了。如果不可能完成所有课程,返回一个空数组。

示例 1:

输入: 2, [[1,0]] 
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。
示例 2:

输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
     因此,一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:

输入的先决条件是由边缘列表表示的图形,而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。

提示:
这个问题相当于查找一个循环是否存在于有向图中。如果存在循环,则不存在拓扑排序,因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程(21分钟),介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。

拓扑排序

class Solution {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
        if(numCourses == 0){
            return result;
        }
        
        if(prerequisites == null || prerequisites.length == 0){
            for(int i = 0; i < numCourses; i++){
                result[i] = i;
            }
            return result;
        }
        
        int[] indegree = new int[numCourses];
        Queue<Integer> zeroDegree = new LinkedList<>();
        for(int[] pre : prerequisites){
            indegree[pre[0]]++;
        }
        for(int i = 0; i < indegree.length; i++){
            if(indegree[i] == 0){
                zeroDegree.add(i);
            }
        }
        if(zeroDegree.isEmpty()){
            return new int[0];
        }
        int index = 0;
        while( !zeroDegree.isEmpty() ){
            int course = zeroDegree.poll();
            result[index] = course;
            index++;
            for(int[] pre : prerequisites){
                if(pre[1] == course){
                    indegree[pre[0]]--;
                    if(indegree[pre[0]] == 0){
                        zeroDegree.add(pre[0]);
                    }
                }
            }
        }
        
        for(int in : indegree){
            if(in != 0){
                return new int[0];
            }
        }
        
        return result;
        
    }
}


参考资料:https://leetcode-cn.com/u/ac_oier/