您的浏览器不支持CSS3，建议使用Firfox、Chrome等浏览器，以取得最佳显示效果

图论基础知识、常用算法与LeetCode题解

开发技术 3,951℃ 3 1年前 (2020-04-06)
推广：微软社招内推可发简历至 [email protected] 或加微信 jzj2015 (注明微软内推并自我介绍)。

摘要

本文介绍图论基础知识，并结合LeetCode分析常用算法。

基本概念

图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

使用 G(V, E) 表示一个图，V为顶点(Vertex)，E为边(Edge)。图中不允许没有顶点，但是可以没有边。

有限图与无限图

有限图：V, E 都是有限集合。

无限图：V 或 E 是无限集合。

有向图与无向图

无向图 (Undirected graph)：每个边都是无向边。

e = (u, v)

  • e：无向边 (Undirected edge)，简称 边 (Edge)
  • u, v：e的 端点 (Endpoint)

有向图 (Directed graph)：每个边都是有向边。

e = u -> v

  • e：有向边 (Directed edge) ，简称弧 (Arc) 或 边 (Edge)
  • u：e 的 起点 (Tail)
  • v：e 的 终点 (Head)
  • u, v：e的 端点 (Endpoint)
  • u 是 v 的直接前驱，v 是 u 的直接后继

为什么起点是 Tail，终点是 Head？
有向边通常用箭头表示，而箭头是从“尾”指向“头”的。

混合图 (Mixed graph)：既有有向边，又有无向边。

相邻

关联（Incident)：顶点 v 是边 e 的一个端点，则称 e 和 v 关联 或 相邻。

邻接 / 相邻（Adjacent）：顶点u和v，若存在边 (u，v)，则称u和v是邻接或相邻的。

邻域 (Neighborhood) ：

  • 顶点 v：所有与顶点 v 相邻的顶点集合，记作 N(v)。
  • 点集 S：与 S 中至少一个点相邻的顶点集合，记作 N(S) ，N(S) = ∪ N(v), v∈S

度

度（degree）：顶点相邻边的数目，常用 deg(V), d(v) 表示。

  • 孤立点 (Isolated vertex) ： d(v) == 0
  • 叶节点 (Leaf vertex) / 悬挂点 (Pendant vertex) ： d(v) == 1
  • 偶点 (Even vertex) ： d(v) % 2 == 0
  • 奇点 (Odd vertex) ：d(v) % 2 == 1。奇点的个数是偶数。
  • 支配点 (Universal vertex) ：d(v) = |V| - 1，和所有其他点都相邻。

有向图中：

  • 入度 (In-degree)：以该顶点为终点的边的数目，常用 d+(v) 表示。
  • 出度 (Out-degree)：以该顶点为起点的边的数目，常用 d-(v) 表示。
  • 顶点的度 = 入度 + 出度，即 d(v) = d+(v) + d-(v)。

自环与重边

  • 自环 (Loop) ：边 e 的两个端点相同，则 e 称为一个自环。
  • 重边 (Multiple edge) ：两个完全相同的边，称作（一组）重边。在无向图中 (u,v) 和(v,u) 算一组重边，而在有向图中，u -> v 和 v -> u 不为重边。

简单图与多重图

  • 简单图 (Simple graph) ：没有自环和重边。非空简单图中一定存在度相同的结点。
  • 多重图 (Multigraph) ：有自环或重边 。

路径

途径 (Walk) / 链 (Chain)：v0, e1, v1, e2, ... ek, vk，或简写为 v0 → v1 → ... → vk

迹 (Trail) ：链，且所有边都不同。

路径（Path）/ 简单路径 (Simple path)：迹，且所有点都不同（除了允许 v0 == vk）。

回路 (Circuit) ：迹，且 v0 == vk。

环 / 圈 (Cycle) / 简单回路 / 简单环 (Simple circuit)：简单路径，且 v0 == vk。

连通

无向图

  • 连通的 (Connected) ：从顶点 u 有路径到达 v ，则 u,v 是连通的。
  • 连通图 (Connected graph)：任意两点连通。
  • 连通分量 / 极大连通子图 (Connected component)：H是G的连通子图，且不存在连通图F，使得 H ⊊ F ⊆ G，则H是G的连通分量。

性质：

  • 连通图只有一个连通分量，即图自身。
  • 非连通图有多个连通分量。

有向图

  • 可达：从顶点 u 有路径到达 v ，则 u 可达 v。
  • 强连通的 (Strongly connected)：有向图中，所有节点互相可达。
  • 弱连通的 (Weakly connected)：有向图中，边替换为无向边后可以得到连通图（也就是有些节点只能单向可达）。
  • 弱连通分量 / 极大弱连通子图 (Weakly connected component) ， 强连通分量 / 极大强连通子图 (Strongly Connected component)：与连通分量类似。

稀疏图与稠密图

稀疏图 (Sparse graph)：边数远小于点数的平方。

稠密图 (Dense graph) ：边数接近点数的平方。

特殊的图

树 (Tree) ：不含环的无向连通图。

森林 (Forest)：多棵树可以组成一个 森林。

二分图 (Bipartite graph)：图的点集分为两部分，每一部分的内部都没有连边（或者说所有边的两个点刚好分别在两部分中）。

完全二分图 (Complete bipartite graph/Biclique)：任何两个不在同一部分的点之间都有连边（例如两部分分别有 x,y 个点，则图总共有x*y个边）。

图的表示

直接存边

使用一个数组来存边，数组中的每个元素都包含一条边的起点、终点和边权（带边权的图），或者使用多个数组分别存起点、终点和边权。

邻接矩阵 Adjacency Matrix

二维数组 adj[][]，adj[u][v] 为 1 表示存在 u 到 v 的边，为 0 表示不存在。

如果是带边权的图，可以在 adj[u][v] 中存储 u 到 v 的边的边权。

邻接矩阵

邻接表 Adjacency Table

使用一个支持动态增加元素的数据结构构成的数组，例如Java中的 List[] adj。

  • 领接表中 adj[u] 存储的是点 u 所有出边的信息（终点、边权等）。

  • 逆邻接表中 adj[u] 存储的是点 u 所有入边的信息（起点、边权等）。

邻接表

图的遍历

  • 深度优先搜索 (Depth-First Search, DFS)
  • 广度优先搜索 (Breadth-First Search, BFS)

拓扑排序问题（有向无环图、AOV网）

有向无环图，Directed Acyclic Graph，DAG

拓扑排序，Topological sorting

AOV网（Activity On Vertex Network)：将一个工程分为多个小的活动（Activity)，在有向无环图中，用顶点表示活动，用弧（有向边）表示活动的先后关系，简称为AOV网。

性质：

  • 能 拓扑排序 的图，一定是有向无环图
  • 有向无环图，一定能拓扑排序

注意：

  • B依赖A，一般在图中表示为有向边 A -> B ，也就是先完成A，后完成B。

LeetCode 210. 课程表 II

210. 课程表 II

现在你总共有 n 门课 0 ~ n-1。想要学习课程 0，要先完成课程 1，用 [0,1] 表示。给定课程总量以及它们的先决条件，返回学完所有课程的顺序（返回一种即可），如果不可能完成所有课程，返回空数组。

Kahn 算法

流程

  1. 将入度为0的节点保存到集合S中（入度为0说明不依赖其他节点）。
  2. 从集合S中取出任意一个节点n，放到结果List中。
  3. 将n的后继节点入度减少1，如果入度变为0，则添加到集合S中（可以理解为从图中删除节点n及其出边，因此后继节点的入度减少了；节点入度变为0时，说明它的依赖节点都已经放好了）。
  4. 不断循环直到集合S为空。
  5. 检查是否所有节点都已经处理。如果有节点没处理，说明有环，无法排序。

复杂度

时间复杂度 O(E + V)

图解

0、A的入度为0，添加到集合S中。

  • 集合S： [A]
  • 排序结果： []

1、移除A。同时B、C的入度也会变为0，添加到集合中。

  • 集合S： [B, C]
  • 排序结果： [A]

2、移除B，同时D的入度变为1，E的入度变为0，添加E到集合S中。

  • 集合S： [C, E]
  • 排序结果： [A, B]

3、移除C，同时D的入度变为0，添加到集合S中。

  • 集合S： [E, D]
  • 排序结果： [A, B, C]

4、移除E。

  • 集合S： [D]
  • 排序结果： [A, B, C, E]

5、移除D，集合S变为空，且所有节点都已经放到了排序结果列表中，排序完成。

  • 集合S： []
  • 排序结果： [A, B, C, E, D]

代码

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] indegree = new int[numCourses];
        for (int[] e : prerequisites) {
            // e[0] depends on e[1]
            // e[1] --> e[0]
            int pre = e[1], cur = e[0];
            List<Integer> list = graph.get(pre);
            if (list == null) {
                list = new LinkedList<>();
                graph.put(pre, list);
            }
            list.add(cur);
            indegree[cur]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        int[] result = new int[numCourses];
        int size = 0;
        while (queue.size() > 0) {
            int node = queue.poll();
            result[size++] = node;
            List<Integer> next = graph.get(node);
            if (next != null) {
                for (int n : next) {
                    indegree[n]--;
                    if (indegree[n] == 0) {
                        queue.offer(n);
                    }
                }
            }
        }

        if (size != numCourses) return new int[0];
        return result;
    }
}

深度优先算法 DFS

流程

  • 从每个未访问的节点开始深度优先遍历。
  • 访问完一个节点的所有后继节点后，将该节点添加到栈中（类似树的后序遍历）。
  • 最后将栈反转即可得到结果。

图解

例如下面的例子：

深度优先可以想象成将图分割为多个树，先后遍历每棵树，且后遍历的树依赖先遍历的树。

  1. DFS(A)：访问了 A, B, D, E ，栈：[E, D, B, A]
  2. DFS(C)：访问了 C, G，栈：[E, D, B, A; G, C]
  3. DFS(F)：访问了 F, H，栈：[E, D, B, A, G, C; H, F]

排序结果：F H C G A B D E 。

代码

DFS实现如下，其中：

  • graph 为邻接表。
  • globalVisited 用于标记所有访问过的节点，已经访问过的不再重复访问。
  • localVisited 用于标记本轮DFS访问过的节点，如果某一轮DFS重复访问到了某个节点，说明图中有环。
public int[] findOrder(int numCourses, int[][] prerequisites) {
    // adjacency list
    Set<Integer>[] graph = new Set[numCourses];
    for (int[] e : prerequisites) {
        // e[0] depends on e[1]
        // e[1] --> e[0]
        if (graph[e[1]] == null) {
            graph[e[1]] = new HashSet<>();
        }
        graph[e[1]].add(e[0]);
    }

    List<Integer> list = new ArrayList<>(numCourses);
    boolean[] globalVisited = new boolean[numCourses];
    boolean[] localVisited = new boolean[numCourses]; // to check cycle

    for (int i = 0; i < numCourses; ++i) {
        if (!dfs(graph, i, globalVisited, localVisited, list)) {
            return new int[0];
        }
    }

    // copy and reverse
    int[] result = new int[numCourses];
    for (int i = 0; i < numCourses; ++i) {
        result[i] = list.get(numCourses - i - 1);
    }
    return result;
}

// return: can finish
public boolean dfs(Set<Integer>[] graph, int node, boolean[] globalVisited, boolean[] localVisited, List<Integer> list) {
    if (localVisited[node]) return false;
    if (globalVisited[node]) return true;
    localVisited[node] = true;
    globalVisited[node] = true;
    Set<Integer> next = graph[node];
    if (next != null) {
        for (Integer n : next) {
            if (!dfs(graph, n, globalVisited, localVisited, list)) {
                // return false and exit, no need to reset localVisited
                return false;
            }
        }
    }
    localVisited[node] = false; // reset
    list.add(node);
    return true;
}

最短路径问题

对于边权为正的图，任意两个结点之间的最短路：

  • 不会经过重复的结点。

  • 不会经过重复的边。

  • 结点数不超过 n ，边数不会超过 n – 1。

单源最短路：指定源点，求它到其余各个结点的最短路。

LeetCode 743. 网络延迟时间

743. 网络延迟时间

有 N 个网络节点 1 ~ N。给定列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。

从节点 K 发送信号，多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

深度优先算法 DFS

流程：

  • 使用数组保存到达每个节点的最小耗时。初始化时节点 K 耗时为0，其他节点均为 -1，表示未访问。
  • 从节点 K 开始深度优先搜索。每当遇到一个节点，且节点未访问 或 新的时间小于节点保存的时间，就更新这个节点的时间（一方面不需要更新为更大的时间，另一方面避免遇到环，导致死循环）。
  • 遍历节点时间数组，如果仍有未访问的节点，说明从节点 K 到该节点不可达，返回 -1；否则返回数组中的最大值。

使用DFS解题（489 ms），性能很差。

class Solution {

    public int networkDelayTime(int[][] times, int N, int K) {
        // time[i]: node [i] receive time
        int[] time = new int[N+1];
        Arrays.fill(time, -1);
        time[K] = 0;

        // graph[i]: List<int[]>, [to node, w]
        List<int[]>[] graph = new List[N+1];
        for (int i = 1; i <= N; ++i) {
            graph[i] = new LinkedList<>();
        }
        for (int[] t : times) {
            int from = t[0], to = t[1], w = t[2];
            graph[from].add(new int[]{to, w});
        }

        dfs(graph, time, K);

        int max = -1;
        for (int i = 1; i <= N; ++i) {
            if (time[i] == -1) return -1;
            max = Math.max(max, time[i]);
        }
        return max;
    }

    public void dfs(List<int[]>[] graph, int[] time, int node) {
        for (int[] t : graph[node]) {
            int to = t[0], w = t[1];
            int newTime = time[node] + w;
            if (time[to] != -1 && newTime >= time[to]) {
                continue;
            }
            time[to] = newTime;
            dfs(graph, time, to);
        }
    }
}

弗洛伊德算法 Floyd-Warshall Algorithm

特点：

  • 可以求任意两个结点之间的最短路。

  • 复杂度较高，但容易实现。

  • 适用于任何图，不管有向无向，边权正负，但是最短路必须存在（不能有个负环）。

思路：

  • 使用矩阵表示节点 u → v 之间的最短路径。
  • 初始化时，w[i][i] 为0， w[i][j] 为边 i → j 的权重，没有边的元素设置为无穷大。
  • 节点 i → j 可能通过 k 中转而缩短距离，遍历计算点 i → k → j 的路径，如果比现有的 i → j 小，则更新，即松弛操作。

复杂度：

  • 时间复杂度 O( N^3 )
  • 空间复杂度 O( N^2 )

使用Floyd算法求解（18ms）。

class Solution {

    public int networkDelayTime(int[][] times, int N, int K) {
        // w[i][j]: time from [i] to [j], Integer.MAX_VALUE: inf
        int[][] w = new int[N+1][N+1];
        for (int i = 1; i <= N; ++i) {
            Arrays.fill(w[i], Integer.MAX_VALUE);
            w[i][i] = 0;
        }

        for (int[] e : times) {
            int u = e[0], v = e[1], t = e[2];
            w[u][v] = t;
        }

        for (int k = 1; k <= N; ++k) {
            for (int i = 1; i <= N; ++i) {
                for (int j = 1; j <= N; ++j) {
                    int sum;
                    if (w[i][k] == Integer.MAX_VALUE || w[k][j] == Integer.MAX_VALUE) {
                        sum = Integer.MAX_VALUE;
                    } else {
                        sum = w[i][k] + w[k][j];
                    }
                    w[i][j] = Math.min(w[i][j], sum);
                }
            }
        }

        int max = -1;
        for (int j = 1; j <= N; ++j) {
            if (w[K][j] == Integer.MAX_VALUE) return -1;
            max = Math.max(max, w[K][j]);
        }
        return max;
    }
}

迪杰斯特拉算法 Dijkstra Algorithm

特点：

  • 求单源最短路径。
  • 只适用于非负权图。
  • 时间复杂度优秀。
  • 使用了贪心思想。

步骤：

  • 初始：
    • 已确定最短路的节点为集合P，未确定最短路的节点为集合Q。
    • 保存源节点 K 到每个节点的距离，初始化时距离为无穷大。
    • 将源节点 K 放入Q，其距离为0。
  • 循环：
    • 从Q取出一个距离最短的节点 u，其最短路径已经确定，因此移到P（贪心思想，因为 K 到其他点的距离更远，不可能找到一个经过其他点再到 u 的更短路径）。
    • 松弛 u 的未确定最短路的出节点，即判断经过 u 能否缩短距离。将这些节点放到Q中等待下一轮循环处理。
    • 继续循环，直到Q为空。

具体实现：

  1. 可以用 int 数组保存每个节点的距离，boolean 数组表示节点是否已经加入到P。
  2. 优化：Java中使用 PriorityQueue 实现Q，这样每次取出距离最短节点时性能更好。

图解1，来自 维基百科：

img

图解2，来自 博客：

图解2的执行步骤分析：

第一行为节点，第二行为距离，.表示无穷大∞，加中括号表示已经确定最短路径

 1    2    3    4    5    6
 0    ·    ·    ·    ·    ·
 ↑                             选1，松弛2、3

 1    2    3    4    5    6
[0]   1   12    ·    ·    ·
      ↑                        选2，松弛3、4

 1    2    3    4    5    6
[0]  [1]  10    4    ·    ·
                ↑              选4，松弛3、5、6...

使用Dijkstra算法求解（24 ms）：

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        // graph[i]: List<int[]>, [to node, w]
        List<int[]>[] graph = new List[N+1];
        for (int i = 1; i <= N; ++i) {
            graph[i] = new LinkedList<>();
        }
        for (int[] e : times) {
            int from = e[0], to = e[1], w = e[2];
            graph[from].add(new int[]{to, w});
        }

        // [distance, node]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        // node --> min distance
        HashMap<Integer, Integer> dist = new HashMap<>();

        heap.offer(new int[]{0, K});

        while (heap.size() > 0) {
            int[] n = heap.poll();
            int distance = n[0];
            int node = n[1];
            if (dist.containsKey(node)) continue; // already determined
            dist.put(node, distance); // node determined
            for (int[] g : graph[node]) {
                int nextNode = g[0];
                int w = g[1];
                // K --> ... --> node --> nextNode
                if (dist.containsKey(nextNode)) continue; // alreay determined
                heap.offer(new int[]{distance + w, nextNode});
            }
        }

        if (dist.size() != N) return -1;
        int max = -1;
        for (int d : dist.values()) {
            max = Math.max(max, d);
        }
        return max;
    }
}

并查集 Disjoint-set

故事：

几个家族进行宴会，但是家族普遍长寿，所以人数众多。由于长时间的分离以及年龄的增长，这些人逐渐忘掉了自己的亲人，只记得自己的爸爸是谁了，而最长者（称为「祖先」）的父亲已经去世，他只知道自己是祖先。

为了确定自己是哪个家族，他们想出了一个办法，只要问自己的爸爸是不是祖先，一层一层的向上问，直到问到祖先。如果要判断两人是否在同一家族，只要看两人的祖先是不是同一人就可以了。

初始化

int[] parent = new int[n];

void init() {
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }
}

查找

int findRoot(int x) {
    int x_root = parent[x];
    while (x_root != x) {
        x_root = parent[x_root];
    }
    return x_root;
}

路径压缩

查找过程中，同时把每个节点都直接连接到根上。这样可以大大提高效率。

// 迭代写法
int findRoot(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

// 递归写法
int findRoot(int x) {
  if (x != parent[x])
    parent[x] = find(parent, parent[x]);
  return parent[x];
}

合并

宴会上，一个家族的祖先突然对另一个家族说：我们两个家族交情这么好，不如合成一家好了。另一个家族也欣然接受了。由于并不在意祖先究竟是谁，所以只要其中一个祖先变成另一个祖先的儿子就可以了。

boolean union(int x, int y) {
    // x 与 y 所在家族合并
    x = find(x);
    y = find(y);
    if (x == y) {  // 原本就在一个家族里就不管了
        return false;
    }
    parent[x] = y;  // 把 x 的祖先变成 y 的祖先的儿子
    return true;
}

启发式合并（按秩合并）

一个祖先突然抖了个机灵：“你们家族人比较少，搬家到我们家族里比较方便，我们要是搬过去的话太费事了。”

路径压缩有时不适用，可以用启发式合并。

int[] rank = new int[n]; // initial value: 0

boolean union(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
        return false;
    }
    if (rank[x] > rank[y]) {
        parent[x] = y;
    } else if (rank[x] < rank[y]) {
        parent[y] = x;
    } else {
        parent[x] = y;
        rank[y]++;
    }
    return true;
}

并查集应用

  • 求连通分量：依次对每个边的两个顶点进行并查集合并，可以使得每个连通分量的root相同，从而得出每个连通分量。
  • 查找环：合并过程中，如果发现一条边的两个顶点已经合并过，说明这两个顶点之前已经通过其他路径合并，再加上这条边，图中就出现了环。
  • 求最小生成树：贪心思想，从小到大排序所有边，使用并查集依次合并，并跳过形成环的边，即可得到最小生成树。

LeetCode 684. 冗余连接

684. 冗余连接

输入一个无向图，该图由有N个节点的树及一条附加的边构成。返回一条可以删去的边，使得结果图是有N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。

分析

  • 依次对每个边的两个顶点进行并查集合并。

  • 当遇到一个边的两个顶点已经合并过，发现了环，返回这条边。

  • 输出参数只有 edges 而没有N。对于有 N 个节点的树，应该有 N-1 条边，再加上附加的一条边，得到N条边。因此 edges 的size即为N。

图解

输入边 [AB, AC, AE, CD, CF, EF]，删掉环路中的每个边都可以组成树，例如AC、AE、CF、EF，按照题目要求，取最后一个即 EF 即可。

遍历过程如下：

  • 遍历AB：合并AB
  • 遍历AC：合并ABC
  • 遍历AE：合并ABCE
  • 遍历CD：合并ABCED
  • 遍历CF：合并ABCEDF
  • 遍历EF：发现节点 E、F 已经合并过了（经过AC、AE、CF合并），说明有环，返回EF。

代码

class Solution {

    int[] parent;

    public int[] findRedundantConnection(int[][] edges) {
        // N = edges.length
        parent = new int[edges.length + 1];
        for (int i = 0; i < parent.length; ++i) {
            parent[i] = i;
        }
        for (int[] edge : edges) {
            if (!union(edge[0], edge[1])) {
                return edge;
            }
        }
        return new int[]{-1,-1};
    }

    public int findRoot(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    public boolean union(int x, int y) {
        x = findRoot(x);
        y = findRoot(y);
        if (x == y) {
            return false;
        }
        parent[x] = y;
        return true;
    }
}

最小生成树

最小生成树（Minimum Spanning Tree，MST）：无向连通图中边权和最小的生成树（最短路径连接所有节点）。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

img

LeetCode 1135. 最低成本联通所有城市

1135. 最低成本联通所有城市

  • 地图上有 N 座城市 1 ~ N。
  • 给出一些 conections，其中 conections[i] = [city1, city2, cost] 表示将城市 city1 和城市 city2 连接所要的成本，连接是双向的。
  • 返回连接所有城市的最小成本，如果无法连接所有城市，返回 -1。

Kruskal算法

Kruskal算法 = 贪心 + 并查集

流程：将所有边按cost从小到大排序，然后使用并查集依次尝试合并每个边：

  • 如果合并成功，则加入这条边。
  • 如果合并失败（边的两个节点已经合并过），说明产生了环，则丢弃这条边。

通过并查集合并后，每个连通分量节点都会有相同的root，因此检查所有节点的root：

  • 如果检查到只有一个root，说明这个图只有一个连通分量，是连通图，返回cost。
  • 如果检查到超过一个root，说明这个图有多个连通分量，不是一个连通图，返回-1。
class Solution {

    public int minimumCost(int N, int[][] connections) {
        // sort connections by cost from small to large
        Arrays.sort(connections, (a,b) -> a[2]-b[2]);

        int[] parent = new int[N+1];
        for (int i = 1; i <= N; ++i) {
            parent[i] = i;
        }

        int cost = 0;
        for (int[] edge : connections) {
            if (union(edge[0], edge[1], parent)) {
                cost += edge[2];
            }
        }

        // check if all the roots are the same
        int p = -1;
        for (int i = 1; i <= N; ++i) {
            int root = findRoot(i, parent);
            if (p == -1) {
                p = root;
            } else if (p != root) {
                return -1;
            }
        }
        return cost;
    }

    public int findRoot(int x, int[] parent) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    public boolean union(int a, int b, int[] parent) {
        a = findRoot(a, parent);
        b = findRoot(b, parent);
        if (a == b) return false;
        parent[a] = b;
        return true;
    }
}

Prim算法

Kruskal算法每次添加一个最小的边，而Prim算法则是每次添加一个距离已选取节点集最近的点。

流程：

  1. 集合S表示已选取的节点集。
  2. 选任意一个节点作为起始节点 a，放到集合S中，并更新其他节点到集合S的最近距离。因为当前S中只有一个节点 a，因此更新为到节点 a 的距离。
  3. 选取距离S最近的一个节点 b，放到集合S中，并更新其他节点到集合S的最近距离。也就是节点 i 的距离更新为 min { adj[a][i], adj[b][i] }。
  4. 继续选取、更新，直到N个节点都被选取。

实际提交发现，Prim算法效果远不如Kruskal好。

  • 题目给的是边（connections），而使用Prim算法，需要快速得到两个节点之间的距离。如果每次都直接遍历connections，复杂度太高，因此需要先转换成邻接矩阵或邻接表。选择合适的邻接矩阵或邻接表，是解决本题的一个关键。

  • 另外一个关键点就是，获取距离最小的节点，可以直接遍历，也可以借助 PriorityQueue 实现。

解法1：超出内存限制

最基础的Prim算法实现，使用二维数组保存邻接矩阵，暴力搜索查找距离最小的节点。

代码应该是正确的，在简单的测试用例中运行是正确的。但是由于邻接矩阵太大，导致超出了内存限制，提交未通过。

class Solution {

    public int minimumCost(int N, int[][] connections) {

        int INF = Integer.MAX_VALUE;

        // graph[i][j]:
        //     INF: not reachable
        //     x: distance
        int[][] graph = new int[N+1][N+1];
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (i == j) graph[i][j] = 0;
                else graph[i][j] = INF;
            }
        }
        for (int[] edge : connections) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u][v] = graph[v][u] = w;
        }

        // dist[i]
        //     d: current min distance from one of added nodes
        //     INF: distance is inf, not reachable
        int[] dist = new int[N+1];
        Arrays.fill(dist, INF);
        // added nodes
        boolean[] added = new boolean[N+1];

        // set node [1] as candidates
        dist[1] = 0;

        int cost = 0;
        for (int k = 0; k < N; ++k) { // N nodes to add

            // find node with min distance
            int min = INF;
            int node = -1;
            for (int i = 1; i <= N; ++i) {
                if (!added[i] && dist[i] < min) {
                    min = dist[i];
                    node = i;
                }
            }

            // no reachable node found
            if (node == -1) {
                return -1;
            }

            // add [node]
            cost += dist[node];
            added[node] = true;

            // update dist[i] with distance from [node] to [i]
            for (int i = 1; i <= N; ++i) {
                if (added[i]) continue;
                if (graph[node][i] == INF) continue;
                dist[i] = Math.min(dist[i], graph[node][i]);
            }
        }
        return cost;
    }
}

解法2：超出时间限制

优化Prim算法，使用HashMap数组保存领接表，借助PriorityQueue选取距离最小的节点。

超出时间限制。

class Solution {

    public int minimumCost(int N, int[][] connections) {

        // graph[i].get(j):
        //     x: distance
        //     null: not reachable
        Map<Integer, Integer>[] graph = new HashMap[N+1];
        for (int i = 1; i <= N; ++i) {
            graph[i] = new HashMap<>();
        }
        for (int[] edge : connections) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].put(v, w);
            graph[v].put(u, w);
        }

        // heap: candidates
        //     int[0]: distance from added nodes
        //     int[1]: node
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[0] - b[0]);
        // added nodes
        boolean[] added = new boolean[N+1];

        // add node [1] to the candidate collection
        heap.offer(new int[]{0, 1});

        int cost = 0;
        for (int k = 0; k < N; ++k) { // N nodes to add

            // find node with min distance
            int[] min = findMin(heap, added);

            // no reachable node found
            if (min == null) {
                return -1;
            }

            int dist = min[0];
            int node = min[1];

            // add [node]
            cost += dist;
            added[node] = true;

            // add candidates with distance from [node]
            for (int i = 2; i <= N; ++i) {
                if (added[i]) continue;
                Integer d = graph[node].get(i);
                if (d != null) { // d == null: not reachable
                    heap.offer(new int[]{d, i});
                }
            }
        }
        return cost;
    }

    public int[] findMin(PriorityQueue<int[]> heap, boolean[] added) {
        while (heap.size() > 0) {
            int[] n = heap.poll();
            int node = n[1];
            if (!added[node]) {
                return n;
            }
        }
        return null;
    }
}

解法3：通过，67 ms

正在怀疑是不是自己写错了Prim算法的时候，借鉴了评论区的思路，重新优化了邻接表的表示方法，使用 HashMap -> List -> int[] 的形式。

这样在更新距离时，不需要再进行复杂的遍历，也不需要创建很多数组（HashMap邻接表和PriorityQueue中的元素格式是相同的，都是 [node, distance]），大大提高了性能。

终于提交通过，耗时67ms。作为对比，Kruskal算法的耗时是27ms，且写起来更容易。

class Solution {

    public int minimumCost(int N, int[][] connections) {

        // graph.get(i).get(x):
        //     int[0]: node
        //     int[1]: distance from [i] to [node]
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] edge : connections) {
            int u = edge[0], v = edge[1], w = edge[2];
            List<int[]> list1 = graph.get(u);
            if (list1 == null) {
                list1 = new LinkedList<>();
                graph.put(u, list1);
            }
            list1.add(new int[]{v,w});

            List<int[]> list2 = graph.get(v);
            if (list2 == null) {
                list2 = new LinkedList<>();
                graph.put(v, list2);
            }
            list2.add(new int[]{u,w});
        }

        // heap: candidates
        //     int[0]: node
        //     int[1]: distance from one of added nodes
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);
        // added nodes
        boolean[] added = new boolean[N+1];

        // add node [1] to the candidate collection
        heap.offer(new int[]{1, 0});

        int cost = 0;
        for (int k = 0; k < N; ++k) { // N nodes to add

            // find node with min distance
            int[] min = findMin(heap, added);

            // no reachable node found
            if (min == null) {
                return -1;
            }

            int node = min[0];
            int dist = min[1];

            // add [node]
            cost += dist;
            added[node] = true;

            // add candidates with distance from [node]
            List<int[]> list = graph.get(node);
            if (list != null) {
                for (int[] e : list) {
                    heap.offer(e);
                }
            }
        }
        return cost;
    }

    public int[] findMin(PriorityQueue<int[]> heap, boolean[] added) {
        while (heap.size() > 0) {
            int[] n = heap.poll();
            int node = n[0];
            if (!added[node]) {
                return n;
            }
        }
        return null;
    }
}

二分图 Bipartite graph

二分图 (Bipartite graph)：节点由两个集合组成，且两个集合内部没有边的图（或者说所有边的两个点刚好分别在两个集合中）。

完全二分图 (Complete bipartite graph / Biclique)：任何两个不在同一部分的点之间都有连边（例如两部分分别有 x,y 个点，则图总共有x*y个边）

性质：

  • 如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。

  • 二分图不存在奇环（长度为奇数的环）。

    因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。

img

LeetCode 785. 判断二分图

785. 判断二分图

以二维数组形式的邻接表方式给出无向图，判断是否为二分图。

思路：

  1. 对节点进行着色，color == 0 表示未着色，color == 1 或 color == -1表示着色。
  2. 从每个未着色的节点开始，将其着色，并进行深度优先搜索（每次深度优先搜索都会遍历完一个连通分量）。
  3. 每遇到一条边，判断其另一个点的颜色：
    • 如果没有着色，就设置成相反的颜色，并继续深入搜索。
    • 如果已经着色，并且和当前点颜色相同，说明不是二分图。
    • 如果已经着色，并且和当前点颜色不同，忽略（继续循环）。

代码：

class Solution {
    public boolean isBipartite(int[][] graph) {
        // 0: uncolored.  1,-1: two oppsite colors
        int[] colors = new int[graph.length];
        for (int i = 0; i < graph.length; ++i) {
            // skip already colored node
            if (colors[i] != 0) continue;
            // set color to 1
            colors[i] = 1;
            // dfs, visit connected components
            if (!dfs(graph, colors, i)) return false;
        }
        return true;
    }

    public boolean dfs(int[][] graph, int[] colors, int node) {
        int color = colors[node];
        int[] nodes = graph[node];
        for (int n : nodes) {
            // found uncolored node, set color to oppsite and search deep
            if (colors[n] == 0) {
                colors[n] = -color;
                if (!dfs(graph, colors, n)) {
                    return false;
                }
            }
            // found node with same color, return false
            if (colors[n] == color) {
                return false;
            }
            // found node with oppsite color, loop continue
        }
        return true;
    }
}

参考资料与扩展学习

OI Wiki：图论部分简介

这一点点的图论基础

数据结构与算法——图论基础与图存储结构

【算法】并查集（Disjoint Set）- Bilibili

最小生成树：Prim算法和Kruskal算法

Leetcode 题解 – 图

Graphviz

使用Graphviz绘图

最后，欢迎扫码关注微信公众号。程序员同行学习交流，聊天交友，国内外名企求职内推（微软 / 小冰 / Amazon / Shopee / Coupang / ATM / 头条 / 拼多多等），可加我微信 jzj2015 进技术群（备注进技术群，并简单自我介绍）。

本文由原创，转载请注明来源：https://www.paincker.com/graph-theory
（标注了原文链接的文章除外）

3

相关文章

评论3条

  1. yxy1994 回复

    好厉害的总结！大爱！
    Prim的解法3，如果在offer到heap的时候加一个限制条件好像会快一点，heap里的无用元素会少一些：
    if (!added[e[0]]) {
    heap.offer(e);
    }
    测试 60 ms -> 44 ms（graph里换成ArrayList 44 -> 42）

  2. yosunpeng 回复

    写得超棒！！！

    1. jzj1993 回复

      谢谢支持~

评论前：需填写以下信息，或 登录

用户登录

忘记密码？