【每日算法Day 51】图

图的表示形式一般为邻接表和邻接矩阵，考察得不多，一般考察到得问题往往和DFS或BFS遍历有关。

LeetCode 133. 克隆图 (opens new window)

题目描述

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。每个节点值 Node.val 都是唯一的

class Node {
    public int val;
    public List<Node> neighbors;
}

示例

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
当然输入和输出中得元素是两个不同的对象。

解题思路

由于是无向连通图，所以可以从给定节点访问到所有节点，而如果A是B的邻居，则B也是A的邻居。如果不去区分节点是否已经访问过的话会产生死循环。那么可以用一个Map来存储节点的访问信息。下面使用DFS进行遍历。

public Node cloneGraph(Node node) {
    if (node==null) return null;
    Map<Node, Node> map = new HashMap<>();
    return dfs(node, map);
}

private Node dfs(Node target, Map<Node, Node> map) {
    //如果递归过程中发现访问过map就不选这条路，继续访问没走过的并创建克隆节点
    if (map.containsKey(target)) {
        return map.get(target);
    }
    ArrayList<Node> list = new ArrayList<>();
    Node replica = new Node(target.val, list);
    map.put(target, replica);
    //必须要先放入map再递归调用，否则内存超限
    for (Node neighbour : target.neighbors) {
        list.add(dfs(neighbour, map));
    }
    return replica;
}

LeetCode 310. 最小高度树 (opens new window)

题目描述

对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。

示例

输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

输出: [3, 4]

解题思路

从外向内进行BFS，每轮遍历并删除出度为1的节点（叶子节点）并将它们的邻居节点出度-1，发现有出度变为1的就放入队列在下一轮中删除。知道某轮开始前发现图中只剩下1个或2个节点，那么剩下的节点就是根节点。

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if(n==1){
        List<Integer> list=new ArrayList<>();
        list.add(0);
        return list;
    }

    //出度表
    int[] degree = new int[n];
    //邻接表，使用map而不是数组的原因是为了便于在后面删除节点，并且能快速获得剩余节点数
    Map<Integer,Set<Integer>> adjacency = new HashMap<>();
    //填充出度表和邻接表
    for (int[] edge : edges) {
        degree[edge[0]]++;
        degree[edge[1]]++;

        adjacency.computeIfAbsent(edge[0], v ->  new HashSet<>()).add(edge[0]);
        adjacency.computeIfAbsent(edge[1], v ->  new HashSet<>()).add(edge[1]);
    }

    //使用队列来约束一轮只删除当前出度为1的节点，因为一轮删除过程中可能会有下一轮的点的出度变为1
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (degree[i] == 1) {
            queue.offer(i);
        }
    }
    while (adjacency.size()>2) {
        //当前轮要删除的节点数
        int size = queue.size();
        while (size-- > 0) {
            //每轮中出度为1的节点就是当前树的叶子节点
            Integer leaf=queue.poll();
            for (Integer integer : adjacency.get(leaf)) {
                //把要删除的节点的所有邻居出度减一，如果发现出度变为1要放入下一轮处理
                if (--degree[integer] == 1) {
                    queue.offer(integer);
                }
            }
            adjacency.remove(leaf);
        }
    }
    return new ArrayList<>(adjacency.keySet());
}