Undirected Graph, BFS

directed graph BFS 里靠 indegree = 0 判断加入队列；

undirected graph BFS 里靠 degree = 0 判断加入队列；

Minimum Height Trees

论坛里看到的，非常赞的思路。 https://discuss.leetcode.com/topic/30572/share-some-thoughts

先说下自己一个 TLE 的初始尝试：根据所有 Edges 建 ArrayList[] 的 Graph，同时存每个点的 Adjacency lists，考虑到是无向图，对于每一个 edge 我们需要在两个 list 中更新才行。然后维护一个 HashMap<> 存着每一个 height 对应的 List<>，然后循环扫描每一个点作为起点进行 BFS，找到最小 height 之后 map.get(height) 就可以了。

然而这种做法的时间复杂度是 O(V * (E + V)) ，每个点都要扫整个 graph ，太高了。

转换一下思路，我们做的事情其实非常近似于 Find Leaves of Binary Tree , 对于一个形状和链表一样的图，我们知道最优解一定是中点；对于一个 inorder traversal array，我们知道 height balanced tree 也一定以中点为 root;

• 在这个 graph 里，我们要找的，其实也是一层一层剥开最外围 nodes 之后，最里面的点。

因此，即使是 undirected graph，degree 也是非常重要的信息，只不过对于 undirected graph 来讲:

• degree = "in"-degree + "out"-degree 而已.

AC代码，速度击败了 95.98 % ~

O(E + V)

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        int[] degrees = new int[n];
        ArrayList[] graph = new ArrayList[n];

        for(int i = 0; i < n; i++){
            graph[i] = new ArrayList<>();
        }

        for(int[] edge : edges){
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
            degrees[edge[0]]++;
            degrees[edge[1]]++;
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < n; i++){
            if(degrees[i] <= 1) queue.offer(i);
        }

        List<Integer> list = new ArrayList<>();
        while(!queue.isEmpty()){
            int size = queue.size();
            list = new ArrayList<>();
            for(int i = 0; i < size; i++){
                int node = queue.poll();
                list.add(node);
                for(int j = 0; j < graph[node].size(); j++){
                    int next = (int)graph[node].get(j);
                    degrees[next] --;
                    if(degrees[next] == 1) queue.offer(next);
                }
            }
        }

        return list;
    }
}

Graph Valid Tree

这题我之前写 union-find 的时候做过了，确实是更快更高效的写法。不过这题也完全可以用 Graph 上的常规 BFS / DFS 求解.

一个非常精炼的 BFS, DFS, Union-Find 做法总结帖子

这题用 BFS 解需要解决这么几个问题：

• 如何正确 detect cycle?

  • 常规 indegree 的话，如果有 cycle 会有一些点因为 indegree 无法进一步缩小的问题永远不被访问，可以记录 visited count;

  • 另一种方法是，用 int[] 表示每个点的状态，其中

    • 0 代表“未访问”；

    • 1 代表“访问中”；

    • 2 代表“已访问”；

  • 如果在循环的任何时刻，我们试图访问一个状态为 “1” 的节点，都可以说明图中有环。

• 如何正确识别图中 connected components 的数量?

  • 添加任意点，探索所有能到达的点，探索完毕数量 +1；

  • 如此往复，直到已探索点的数量 = # of V in graph 为止。

BFS 做法，时间复杂度 O(E + V);

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        int[] states = new int[n];
        ArrayList[] graph = new ArrayList[n];

        for(int i = 0; i < n; i++){
            graph[i] = new ArrayList();
        }

        for(int[] edge : edges){
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        Queue<Integer> queue = new LinkedList<>();

        queue.offer(0); 
        states[0] = 1;
        int count = 0;

        while(!queue.isEmpty()){
            int node = queue.poll();
            count ++;
            for(int i = 0; i < graph[node].size(); i++){
                int next = (int) graph[node].get(i);

                if(states[next] == 1) return false ;
                else if(states[next] == 0){
                    states[next] = 1;
                    queue.offer(next);
                }
            }
            states[node] = 2;
        }

        return count == n;
    }
}

Clone Graph

一次 AC ~ 由于不用考虑环和拓扑顺序，BFS 的方式就很简单，记录下看过哪些点就可以了。

参考了下论坛讨论之后，不太同意大多数解法，因为假设所有点的 label 唯一不是很适合 generalize 这个算法。用 HashMap<> 实现 Node - Node mapping 比较靠谱。

下面的代码简化了一下，参考了九章的写法，先用一个 getNodes 函数返回所有的节点(因为函数就给了一个)，在返回的时候直接 new ArrayList<>(set) 调用 Collection constructor.

这样算法逻辑就分成两步：

• 过一遍所有节点，建新节点放到 HashMap 中；

• 再过一遍所有节点，这次更新每个对应节点的 neighbors.

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) return node;

        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();

        List<UndirectedGraphNode> nodeList = getNodes(node);

        for(UndirectedGraphNode cur : nodeList){
            map.put(cur, new UndirectedGraphNode(cur.label));
        }

        for(UndirectedGraphNode cur : nodeList){
            UndirectedGraphNode copy = map.get(cur);

            for(UndirectedGraphNode neighbor : cur.neighbors){
                copy.neighbors.add(map.get(neighbor));
            }
        }

        return map.get(node);
    }

    private List<UndirectedGraphNode> getNodes(UndirectedGraphNode node){
        Set<UndirectedGraphNode> visited = new HashSet<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();

        queue.offer(node);
        visited.add(node);

        while(!queue.isEmpty()){
            UndirectedGraphNode cur = queue.poll();
            for(UndirectedGraphNode next : cur.neighbors){
                if(!visited.contains(next)){
                    visited.add(next);
                    queue.offer(next);
                }
            }
        }

        return new ArrayList<>(visited);
    }
}

Copy List with Random Pointer

链表也是图啊，就是这么简单，轻松，愉快~~

这题还有一个比较妖孽的 follow-up，不让用 HashMap. 做法就是在每个节点后面插入新节点，最后再拆出来就行了，复杂度依然 O(n).

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();

        RandomListNode cur;

        for(cur = head; cur != null; cur = cur.next){
            map.put(cur, new RandomListNode(cur.label));
        }

        for(cur = head; cur != null; cur = cur.next){
            RandomListNode copy = map.get(cur);

            copy.random = map.get(cur.random);
            copy.next = map.get(cur.next);
        }

        return map.get(head);
    }
}