【算法】图总结

一、前言

图： 由集合顶点（Vertex） 和 边（Edge） 构成。定义为 G=(V, E)。

• 无向图：边无方向。
• 有向图：边带方向。

图的表示有： 邻接表和邻接矩阵。

• 邻接表： 列表嵌套列表。
• 邻接矩阵： 二维数组; 0 不相通，1 相通。

图的遍历方式有： BFS 和 DFS 。

二、题目

（1）图的深拷贝

LeetCode 133

题干分析

这个题目说的是，给你一个无向图，你要返回这个图的深拷贝。

# 比如说，给你的图是：
​
    1 --- 2
   / \   /
  /   \ /
 4 --- 8
​
# 你要返回这个图的一份深拷贝，为了和原图区分，我们记为：
​
    1’--- 2’
   / \   /
  /   \ /
 4’--- 8’
​
# 每个图节点可以表示成它的节点值以及它相邻的节点。比如这个图，可以表示成：
​
 1: 2, 4, 8
 2: 1, 8
 4: 1, 8
 8: 1, 2, 4
​
拷贝图本质上就是把这组结构再复制一遍即可。

思路分析

思路：DFS （递归）

1. 哈希表（HashMap） ：存储老节点 和 新节点。
2. 递归处理节点

AC 代码：

// Time: o(n ^ 2), Space: o(n), Faster: 68.95%
public Node cloneGraph2(Node node) {
    if (node == null) return null;
    // 1. 存储老节点 和 新节点
    Map<Node, Node> map = new HashMap<>();
    // 2. 递归处理节点
    traverse(node, map);
​
    return map.get(node);
}
​
private void traverse(Node node, Map<Node, Node> map) {
    if (node == null || map.containsKey(node)) return;
​
    Node copyNode = new Node(node.val, new ArrayList<>());
    map.put(node, copyNode);
​
    for (Node neighbor : node.neighbors) {
​
        traverse(neighbor, map);
        copyNode.neighbors.add(map.get(neighbor));
    }
}

（2）高度最小的树

LeetCode 310

题干分析

这个题目说的是，给你一个没有环的无向图，把图上任意一个节点当作根节点，就可以把它看作一棵树。这样一来，对于一个包含 n 个节点的无环无向图，可以产生 n 棵不同的树。你要找出这 n 棵树中，所有高度最小的树，并返回它们的根节点。其中，高度的定义是：根节点和最远的叶子节点之间，边的数量。

注意，给你的 n 是一个正整数，表示图上共有 n 个节点，编号从 0 到 n-1。另外给你一组数字对，表示连接两个节点的边。并且给你的这组数字对中，不包含重复的边。

# 比如说，给你的 n 等于 4，给你的表示边的数字对是：
[0, 1]，
[0, 2]，
[0, 3]
​
# 它表示这样一个无向图：
  1
  |
  0
 / \
2   3
​
# 在这个无向图中，高度最小的树只有一棵，就是以 0 为根节点的树。于是返回：[0]。
​
# 如果把 n 改成 5，然后再加一条边 [3, 4]，这个无向图就会变成：
  1
  |
  0
 / \
2   3
    |
    4
​
# 在这个无向图中，高度最小的树有两棵（高度为 2），返回它们对应的根节点是：[0, 3]。

思路分析

思路方法有二： 暴力法 和 收缩法。

方法一：暴力法，遍历每个节点（时间容易超时）

1. 构建图：无向图，邻接表
2. 遍历每个节点
3. 求结果

AC 代码：

// Time: O(n ^ 2), Space: O(n), Faster: Time Limit Exceeded
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
​
    if (n <= 1 || edges == null) return Collections.singletonList(0);
​
    // 1. 构建图
    List<List<Integer>> g = new ArrayList<>(n);
    for (int i = 0; i < n; ++i) g.add(new ArrayList<>());
    for (int[] e : edges) {
        g.get(e[0]).add(e[1]);
        g.get(e[1]).add(e[0]);
    }
​
    boolean[] visited = new boolean[n]; // 用于是否被访问过
    int[] heights = new int[n];         // 用于记录从某个节点出发，得到的最高高度
    int[] max = new int[]{0};           // 用于地址传参
    int minHeight = Integer.MAX_VALUE;
​
    // 2. 遍历每个节点
    for (int i = 0; i < n; ++i) {
        // 访问图
        dfs(g, visited, i, 0, max);
        heights[i] = max[0];
        if (heights[i] < minHeight) minHeight = heights[i];
        max[0] = 0;
    }
​
    // 3. 求结果
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
        if (heights[i] == minHeight) result.add(i);
    }
    return result;
}
​
private void dfs(List<List<Integer>> g, boolean[] visited,
                 int node, int dist, int[] max) {
    visited[node] = true;
    if (dist > max[0]) max[0] = dist;
    for (int v : g.get(node)) {
        if (!visited[v]) dfs(g, visited, v, dist + 1, max);
    }
    visited[node] = false;
}

方法二：收缩法，逐渐减少边

推论：高度最小的树，它的根节点应该在图的中心

1. 构建图： 邻接表
2. 先统计每个节点的度
3. 遍历叶节点： 直至剩余节点数 == 叶子总数（只会是 1 个 或者 2 个节点）

AC 代码：

// Time: O(n), Space: O(n), Faster: 80.51%
public List<Integer> findMinHeightTreesShrink(int n, int[][] edges) {
    if (n == 1) return Collections.singletonList(0);
​
    // 1. 构建图：邻接表
    List<List<Integer>> g = new ArrayList<>(n);
    for (int i = 0; i < n; ++i) {
        g.add(new ArrayList<>());
    }
    for (int[] e : edges) {
        g.get(e[0]).add(e[1]);
        g.get(e[1]).add(e[0]);
    }
​
    // 2. 统计每个节点的度
    int[] degree = new int[n];
    LinkedList<Integer> leaves = new LinkedList<>(); // 叶节点，度为1的点
    for (int i = 0; i < n; ++i) {
        degree[i] = g.get(i).size();
        if (degree[i] == 1) leaves.add(i);
    }
​
    // 3. 遍历
    while (leaves.size() < n) {
        int size = leaves.size();
        n -= size;
        for (int i = 0; i < size; ++i) {
            int leaf = leaves.poll();
            for (int v : g.get(leaf)) {
                --degree[v];
                if (degree[v] == 1) leaves.add(v);
            }
        }
    }
    return leaves;
}

\